[Hello Coding 알고리즘] 2장. 선택 정렬

[210630]

(어제에 이어서 작성)

Hello Coding 알고리즘

2장. 선택 정렬

배열, 연결리스트, 선택 정렬에 관해 공부한다.

메모리가 동작하는 방법

컴퓨터 메모리의 동작 방식.

• 엄청나게 많은 서랍이 있고, 각 서랍에는 주소가 붙어 있다.
• 메모리에 무언가를 저장할 때는 컴퓨터에게 공간을 요청한다.
• 여러 개의 원소를 저장할 때, '배열'과 '리스트' 두 방식 중 하나를 선택한다.

배열 vs 연결 리스트

배열 (array)

• 친구들과 영화를 보러 가서 자리를 찾을 때에 비유할 수 있다.
• 3명이서 좌석을 예약했는데 한 명이 더 왔다면, 4명이서 붙어 앉을 수 있는 좌석으로 다 같이 옮겨 앉아야 함
• 배열의 모든 원소는 같은 자료형이어야 한다.
• 장점 : READ가 빠르다.
  • 인덱스 index : 배열에서는 모든 원소의 주소를 다 알고 있다.
    • 인덱스는 1이 아니라 0부터 시작. (0, 1, 2, 3 ...)
  • 즉 배열에서는 배열 안의 어떤 원소든 바로 찾을 수 있다. (O(1) , 고정 시간)
  • 임의의 원소 값을 찾는 데 최적이다.
• 단점 : INSERT, DELETE가 느리다.
  • INSERT - 공간이 모자라면, 매번 배열의 모든 원소를 메모리의 새로운 위치로 옮겨야 한다. (O(n) , 선형 시간)
  • 순서를 바꿀 때도 뒤에 오는 모든 원소의 위치를 바꾸어야 하기 때문에 느리다.
  • DELETE - 마찬가지로 삭제한 원소 때문에 다른 원소들을 옮겨야 하기 때문에 느리다. (O(n), 선형 시간)
• 보완 : 만약을 대비해 미리 n개의 자리를 예약한다
  • 한계 1 : 만약의 경우가 생기지 않는다면 메모리를 낭비하게 됨
  • 한계 2 : n개보다도 배열이 커진다면 또 다시 모든 원소를 옮겨야 함

연결 리스트 (linked list)

• 보물찾기에 비유할 수 있다.
  • 1번째 장소로 가면 '다음으로 2번째 장소 ~ 로 가시오', 2번째 장소로 가면 '다음으로 3번째 장소 ~로 가시오' ...
• 연결 리스트 사용 시, 원소를 메모리의 어느 곳에나 둘 수 있다.
  • 영화 보러 가서 4명이 붙어 앉을 수 있는 자리가 없다면 각자 흩어져서 영화를 보는 것과 비슷.
• 각 원소마다 리스트의 다음 원소에 대한 주소가 저장되어 있다.
• 장점 : INSERT, DELETE가 빠르다.
  • INSERT - 메모리의 아무 곳에나 데이터를 넣고, 그 주소를 바로 앞 원소에 저장하면 됨 (O(1), 고정 시간)
  • 순서를 바꿀 때도 주솟값만 수정하면 되므로 매우 쉽다.
  • DELETE - 마찬가지로 데이터 삭제 후 앞 원소에서 주솟값을 삭제하면 되므로 빠름 (O(1), 고정 시간)
• 단점 : READ가 느리다.
  • 원하는 데이터의 주소를 바로 알 수 없기 때문에, 그 데이터의 주솟값을 가진 이전 데이터들을 전부 찾아야 함 (O(n), 선형 시간)
  • 모든 원소의 값을 한 번에 읽는 데에는 좋지만, 특정 원소를 조회할 때는 연결 리스트는 최악임.

인덱스 index

원소의 위치 번호. 0부터 시작한다.

[10, 20, 30, 40] 이라는 배열에서, 원소 20은 인덱스 1에 있다.

임의 접근 vs 순차 접근

임의 접근 random access

• 조회를 위해 해당 원소로 바로 접근하는 방식 (ex. 배열)

순차 접근 sequential access

• 조회를 위해 원소를 첫 번째부터 하나씩 읽는 방식 (ex. 연결 리스트)

선택 정렬 selection sort

어떤 목록을 정렬하기 위해 원소마다 전체 리스트를 조회하고, 새 목록에 이를 기록함.

동작원리

예를 들어 플레이리스트를 많이 들은 곡 - 적게 들은 곡 순서로 정렬하고 싶을 때,

1. 전체 목록을 돌며 가장 많이 들은 곡을 찾는다 (O(n))
2. 새 목록에 그 곡을 기록한다
3. 전체 목록을 돌며 두 번째로 많이 들은 곡을 찾는다 (O(n))
4. 새 목록에 그 곡을 기록한다
5. 목록 전체를 정렬할 때까지 반복한다.

시간 계산 : 목록의 모든 원소를 조회하는 작업을 원소의 갯수만큼 반복함. 따라서 O(n x n) = O(n제곱) 만큼 걸림.

※ 매 반복마다 조회할 목록은 줄어들지만, 빅오표기법에서는 상수항을 무시하기 때문에 O(n제곱) 으로 표기한다.

특징

깔끔한 알고리즘이지만 빠르지 않다.

선택정렬 코드

배열을 작은 정수에서 큰 정수 순으로 정렬하는 코드.

배열에서 가장 작은 원소를 찾는 함수를 작성하고, 그 함수를 이용해 정렬한 결과를 새 배열에 담는다.

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest: ## 설정한 최솟값보다 배열의 i번째 값이 작다면
            smallest = arr[i] ## 그 값이 최솟값이 된다
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print selectionSort([5, 3, 6, 2, 10])