이것이 코딩테스트다 - 10일차

주제

sort

정렬

무작위적인 데이터를 순차적으로 나열하는 것이다.

예시

오름차순 정렬

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

내림차순 정렬

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

선택정렬

요소들 중 가장 작은 것을 골라 맨 앞에 있는 요소와 위치를 바꾼다.

스와프

요소들의 위치를 변경해준다.

array = [6, 8]
array[0], array[1] = array[1], array[0]
print(array) # [8, 6]

시간복잡도

O(N^2)

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

for i in range(len(array)):
    for j in range(i + 1, len(array)):
        if array[i] > array[j]:
            array[i], array[j] = array[j], array[i]
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입정렬

맨 첫번째 요소는 정렬이 되었다고 가정한 후 나머지 요소를 맨 첫번째 요소랑 비교 후 위치를 바꾼다.

시간복잡도

O(N^2)

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

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break

print(array)