정렬

✅ 정렬

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

• 프로그램 데이터를 가공할 대 오름차순이나 내림차순 등 정렬해서 사용하는 경우가 많음

• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 가능 ➡ 이진 탐색의 전처리 과정

• 컴퓨터는 데이터의 규칠성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야함

정렬 설명에서 사용할 예시

💜 선택 정렬

✔ 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정

<step1> 전체 중에서 가장 작은 데이터를 선택하여 맨 앞의 데이터와 바꿈

<step2> 정렬된 첫번재는 제외하고 이후 데이터 중 가장 작은 데이터를 선택해서 처리되지 않은 데이터 중 
	가장 앞에 있는 데이터와 바꿈

<step3> 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복하면 마지막 데이터는 가만히 두어도 
    	이미 정렬된 상태이므로 정렬을 마침

🧡 선택 정렬 코드

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

for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] #값 바꾸기

🔔 선택 정렬의 시간 복잡도

O(N^2)

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

• 매번 가장 작은 수를 찾기 위해서 비교 연산 필요

• N + (N - 1) + (N - 2) + ... + 2 ➡ 근사치 : N * (N - 1)

💜 삽입 정렬

✔ 특정한 데이터를 적절한 위치에 '삽입'한다는 의미

• 선택 정렬에 비해 시간 측면에서 더 효율적인 알고리즘

• 필요할때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을때' 훨씬 효율적

• 두 번째 데이터 부터 시작 ➡ 그 자체로 정렬되어있다고 판단

<step1> 첫번재 데이터는 정렬되어있다고 판단하고 두번째 데이터가 어디로 들어갈지 판단하여 
	7의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재, 7의 왼쪽에 삽입

<step2> 이어서 9가 어떤 위치에 들어갈지 판단 ➡ 삽입 가능한 위치는 총 3가지이며 현재는 9는 5와 
  	7보다 크기 때문에 원래 그대로 둠

<step3> 이어서 0이 어떤 위치에 들어갈지 판단 ➡ 0은 5, 7, 9와 비교했을 때 가장 작기 때문에 
  	첫번재 위치에 삽입

<step3> 삽입하는 과정을 N-1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

🧡 삽입정렬 코드

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

for i in range(len(array)):
    for j in range(i, 0, -1): #인덱스 i부터 1까지 감소하며 반복
        if array[j] > array[j-1]:
            array[j], array[j-1] = array[j-1], array[j] #값 바꾸기
        else: #자기보다 작은 원소를 만나면 멈춤
            break

🔔 삽입 정렬의 시간 복잡도

O(N^2)

• 반복문이 2번 중첩되어 사용

• 최선의 경우에는 O(N)

💜 계수 정렬

✔ 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

• 데이터 개수가 N, 데이터 중 최댓값이 K이일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K) 보장

• 데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을 때만 사용

• 가장 큰 데이터와 가장 작은 데이터의 모든 범위를 담을 수 있는 크기의 리스트를 선언

<step1> 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 ➡ 크기가 10인 리스트 선언

<step2> _7_ 5 9 0 3 1 6 2 9 1 4 8 0 5 2

<step3> _7 5_ 9 0 3 1 6 2 9 1 4 8 0 5 2

<step3> _7 5 9 0 3 1 6 2 9 1 4 8 0 5 2_

• 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록 ex) 5 ➡ 2번

출력결과 : 00

🧡 계수 정렬 소스코드

array = [7,5, 9, 0, 3, 1, 6, 2, 4, 8, 0, 5, 2]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
    
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

🔔 삽입 정렬의 시간 복잡도

O(N + K)

• 데이터를 하나씩 확이한면서 리스트에서 적절한 인덱스의 값을 1씩 증가

• 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터중 최댓값의 크기만큼 반복 수행