정렬

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것.

선택 정렬

• 가장 작은 데이터를 골라서 맨 앞의 원소와 바꾸고, 그 다음으로 작은 데이터를 골라서 맨 앞에서 2번째 원소와 바꾼다.

• 각 원소들을 방문하고, 방문했을 때 작은 원소들을 찾아 탐색해야 하므로(for문 2번) 시간 복잡도는 O(N^2)가 된다.

  • 데이터가 늘어날수록 걸리는 시간은 2의 제곱으로 늘어나게 된다.

import time

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

start_time_1 = time.time()
data_with_python_sort = sorted(data)
end_time_1 = time.time()

start_time_2 = time.time()
for i in range(len(data) - 1):
    for j in range(i + 1, len(data)):
        if data[i] > data[j]:
            data[i], data[j] = data[j], data[i]
end_time_2 = time.time()
            
data_with_selection_sort = data.copy()

print("###### python sort ######")
print(data_with_python_sort)
print(end_time_1 - start_time_1)
print()
print("###### selection sort ######")
print(data_with_selection_sort)
print(end_time_2 - start_time_2)

// 캐시 덕분에 2번째 부터는 각각 7e-7 가량 걸리는 시간이 감소되었다.

삽입 정렬

*ex. 6 5 9 7 3

• 각 원소들을 방문하면서, 방문 중인 원소가 본인의 자리를 찾아 삽입되는 방식이다.
• for문을 통해 오른쪽으로 방문해 나간다고 가정하면, 방문한 원소들끼리는 방문한 원소들끼리 비교했을 때 정렬된 형태를 유지하게 된다.
  • 맨 처음 원소는 정렬되어 있다고 가정하게 된다.(방문할 당시, 본인 밖에 없으니까)
    • ex. 방문할 당시 6은 자기 혼자 밖에 없으니 정렬되어 있는 셈이다.
  • 이미 방문된 원소들은, 방문된 원소들끼리 정렬된 셈이다.
• 방문 중인 원소가 왼쪽으로 비교해가며 자신보다 큰 것을 만나게 되면 그 큰 것 다음에 자신이 삽입되면 된다.
  • ex. 5를 방문할 때 5가 6의 왼쪽으로 삽입된다. 5 6 9 7 3
    • 7은 6을 만났을 때 멈추고, 6의 오른쪽으로 삽입된다.
• 각 원소들을 방문하고, 방문한 원소는 제자리를 찾아가는 방식인데, 본인보다 큰 것을 만나게 되면 바로 해당 차례의 for문을 멈추게 된다.
  • 정렬이 어느 정도 되어 있는 배열에 삽입 정렬을 적용하게 되면 바로바로 멈출 확률이 높아져 시간을 단축시키게 된다.

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

# for i in range(1, len(data)):
#     tmp = i
#     for j in range(i - 1, -1, -1):
#         if data[tmp] < data[j]:
#             data[tmp], data[j] = data[j], data[tmp]
#             tmp = j
#         else:
#             break

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

퀵 정렬