[알고리즘] 정렬 (1)

* 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다.

---

출처

동빈나 이코테

 

 

■ 정렬

● 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것

● 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨

 

 

정렬의 종류와 예제에 대해서 알아보자!

---

■ 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

 

 

■ 선택 정렬 소스코드(Python)

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] # 스와프
    
print(array)

▲ 첫 번째 인덱스를 기준으로 뒤에 모든 인덱스를 반복하면서 첫 번째와 비교하여 보다 작으면 자리를 바꾼다.

 

 

■ 선택 정렬의 시간 복잡도

● 선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

● 구현 방식에 따라 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.

N + (N - 1) + (N - 2) + ... + 2

● 이는 (N² + N - 2) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²) 이라고 작성.

● 등차수열의 형태로 연산 횟수가 구성됨.

 

---

 

■ 삽입 정렬

● 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

● 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작.

 

 

 

 

■ 삽입 정렬 소스코드(Python)

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): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
    	if array[j] < array[j - 1]
        	array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break
            
print(array)

 

여기서 range 함수를 잠깐 살펴보자면
range(start, stop, step)
range(20, 0, -2) 라면
20, 18, 16, 14, 12, 10, 8, 6, 4, 2 의 결과가 나온다.
step으로 음수를 지정할 수 있다. # 단, 끝 숫자는 해당 범위에 포함되지 않는다는 것에 주의하자.

 

 

■ 삽입 정렬의 시간 복잡도

● 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.

● 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

    - 최선의 경우 O(N)의 시간 복잡도를 가진다.

  

● 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행한다면??

- 오름차순정렬을 수행할 때 이미 오름차순으로 되어있으면 각 원소가 들어갈 위치를 고를 때 선형탐색을 하게 되는데 그러한 탐색 과정이 바로 멈춰지기 때문에 왼쪽과 비교해서 바로 멈추기 때문에 사실상 왼쪽 데이터 중에서 자기가 어디로 들어갈지 고르는 시간이 단순히 상수시간으로 대체된다.