정렬 알고리즘(with python)

• 선택 정렬

• 삽입 정렬

• 퀵 정렬

• 계수 정렬

병합 정렬은 이 내용에서는 다루지 않았는데 그 이유는 파이썬에서는 sorted함수를 사용하게 되면, 병합 정렬과 동일한 결과값을 나타내기 때문이다. 따라서 병합 정렬 내용은 다루지 않았다

 

 

• 선택 정렬

데이터가 무작위로 여러 개 있을 떄 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것

 

시간 복잡도: O(N^2)

 

 

코드로 구현할 때는 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다

 

이것을 코드로 구현하게 되면 위와 같이 구현할 수 있다.

가장 작은 원소의 인덱스를 변수로 두고 이 값보다 작은 값이 있으면 교환하는 것을 반복적으로 실행하면 된다.

 

• 삽입 정렬

선택 정렬과 비교하면 실행 시간 측면에서 더 효율적인 알고리즘으로 알려져 있다.

데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬 알고리즘이다.

 

삽입 정렬은 첫 인덱스부터 끝까지 비교하게 되는데 이 때, 마지막을 가게 되면

마지막에 있는 값은 첫 번째부터 마지막-1번째 값까지 비교하여 값이 결정된다.

 

시간 복잡도: O(N^2)

but, 선택 정렬보다는 낫다

 

쉬운 코드이므로 코드 분석은 따로 하지 않았다

위와 같이 선택 정렬과 매우 유사하지만 두번째 for문에서 인덱스 i 부터 1까지 감소하며 앞의 값들과 비교를 반복하는 문장을 써주는 것을 주의하면 된다.

 

시간 복잡도: O(N^2)

 

• 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것

 

 

피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다

그 다음 큰 데이터와 작은 데이터의 위치를 교환해준다

 

 

파이썬의 장점을 살리게 되면 위와 같이 간단하게 퀵 정렬 알고리즘을 구현할 수 있다.

pivot이라는 변수를 두고 첫 번째 원소를 pivot에 넣고 나머지를 tail이라는 변수에 넣는다

 

그리고 left_side는 pivot보다 작은 원소들을, right_side는 피봇보다 큰 수들을 넣게 된다. 

이를 분할 이후 재귀를 써서 왼쪽 부분과 오른쪽 부분을 계속해서 반복하여 배열의 길이가 1이 될 때까지 수행해준다

 

시간 복잡도: O(NlogN)

 

위의 다른 정렬 알고리즘보다 시간 복잡도의 효율 측면에서 가장 좋은 것을 알 수 있다

그러나 평균적으로 시간복잡도가 NlogN이지만 최악의 경우에는 O(N^2)이 될 수 있다.

이는 이미 정렬되어 있는 데이터를 퀵 정렬을 수행하게 되면 매우 느리게 작동하는데 이 때가 최악의 경우에 해당한다

 

 

• 계수 정렬

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

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

 

계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성해준다.

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수정렬이 완료된다.

 

결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다.

 

처음에 count라는 변수를 만들고, 모든 값은 0으로 초기화하며 array에 포함된 값 중 max값만큼의 size를 가지게 된다.

이 값을 0부터 max값만큼 순차적으로 값을 넣어준다

 

그리고 array에 포함된 값을 확인하여, 각각의 인덱스값에 대하여 등장한 횟수만큼을 리스트에 기록한다.

 

해당 값을 출력하게 되면 정렬된 값이 출력된다

 

시간 복잡도: O(N+K)

 

따라서 현존하는 정렬 알고리즘 중에 가장 빠르다

 

공간 복잡도: O(N+K)

 

단점: 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 동일한 값을 가지는 데이터가 여러 개 등장할 때는 적합하지만 데이터의 크기가 100만이 될 정도로 큰 숫자를 가지게 되면 비효율적이다.

 

마지막으로 데이터의 특성을 파악하기 어렵다면 보통 퀵 정렬을 사용하는 것이 가장 적합하다