[Algorithm] 정렬 - 1 #선택, 삽입 정렬

정렬로 이진 탐색 가능

주로 나오는 정렬 : 선택, 삽입, 퀵, 계수 정렬

 

[선택 정렬]

- 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고

- 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복

- 처음 인덱스를 기준으로 그 뒤에 있는 데이터들이랑 비교

ary = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(ary)):
    min_idx = i ## 가장 작은 원소의 인덱스

    for j in range(i+1, len(ary)): # 기준이 되는 인덱스 이후의 데이터들
        if ary[j] < ary[min_idx]:
            min_idx = j ## 이렇게 해야 다음 행에서 정렬 할 수 있음 (자리 위치 변경)

    ary[i], ary[min_idx] = ary[min_idx], ary[i]

print(ary)

- (N-1) 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함

연산 횟수 : N + (N-1) + .. + 2 ==> O(N^2) 

- 만약 데이터가 100배 늘어나면 수행 시간은 10,000배 늘어남.. (어마어마!!)

- 선택 정렬은 매우 비효율적인 알고리즘이지만, 어떤 문제에서는 가장 작은 데이터를 찾는 일이 있을 수 있음 - 이때는 선택 정렬 사용

 

[삽입 정렬]

- 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입

- 필요할 때만 위치를 바꾸므로 만약! 데이터가 거의 정렬 되어 있다면 완전 효율적인 문제이다!

- 삽입 정렬은 두번째 데이터부터 시작한다는 것이 특징 (왜? 첫번째 데이터는 그 자체로 정렬 되어 있다고 판단)

- 이런 식으로 기준이 되는 인덱스 앞에 위치한 데이터들은 정렬 되어 있다고 가정

- 만약 현재 값이 들어갈 곳이 있다면 이동, 그렇지 않다면 원래 자리 그대로 있음

- 참고로, 현재 인덱스를 기준으로 왼쪽 순서대로 살펴보면 자리가 있다면 왼쪽으로 이동(여기서는 카드를 오름차순 기준으로 하기 때문에 왼쪽으로만 이동)

ary = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(ary)):
    for j in range(i, 0, -1): # 기준이 되는 인덱스 이후의 데이터들
        if ary[j] < ary[j-1]: ## 왼쪽으로 이동해야하는 경우
            ary[j], ary[j-1] = ary[j-1], ary[j]
        else:## 자기보다 작은 데이터 발견하면 현재 그자리에서 멈추기!!!
            break


print(ary)

- 삽입 정렬의 시간 복잡도 또한 이중 반복문을 사용하기 떄문에 O(N^2)

- (중요!! **) 삽입 정렬은 현재 리스트의 데이터가 거의 정렬 되어 있으면 매우 빠르게 동작

- 거의 정렬이 되어 있다면 퀵 알고리즘 보다 더 강력함!!!!

 

Ref : 나동빈, "이것이 코딩테스트다"