정렬 알고리즘
선택 정렬
리스트의 데이터 중 가장 작은 것을 선택해 맨 앞에 있는 것과 바꾸고, 그 다음으로 작은 것을 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하여 데이터를 정렬한다.
시간 복잡도
N-1번 만큼 가장 작은 수를 찾아서 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위한 비교 연산도 필요하다. 따라서 연산 횟수는 N + (N - 1) + (N - 2) + ··· + 2로, N * (N + 1) / 2이라고 할 수 있다. 빅오 표기법에 따라 O(N^2)로 간단히 표현할 수 있다.
선택 정렬에서는 일반적으로 반복문이 2번 중첩되어 사용되기 때문에 시간 복잡도가 O(N^2)라고 직관적으로 이해할 수도 있다.
특징
• 정렬할 데이터가 늘어날 수록 정렬 속도가 급격히 느려진다.
삽입 정렬
데이터를 하나씩 확인하여 적절한 위치에 삽입하여 정렬한다.
시간 복잡도
선택 정렬 알고리즘과 마찬가지로 반복문이 2중으로 사용되었다. 따라서 일반적인 경우 O(N^2)의 시간 복잡도를 가진다. 하지만 리스트의 데이터가 거의 정렬되어 있는 상태라면 효율성이 급격히 상승하여, 최선의 경우 O(N)의 시간 복잡도를 가질 수 있다.
특징
• 필요한 경우에만 데이터의 위치를 바꾸므로 데이터가 정렬되어 있을 때 훨씬 효율적이다.
• 정렬이 이루어진 원소는 어떤 단계든지 항상 오름차순을 유지하고 있다.
퀵 정렬
먼저 가장 왼쪽 값을 피벗으로 설정한다. 그리고 왼쪽에서부터 피벗보다 작은 데이터를, 오른쪽에서부터 피벗보다 큰 데이터를 선택하여 서로 자리를 변경한다. 만약 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 엇갈린 경우, 작은 값과 피벗의 자리를 교체한다. 이후로는 피벗의 왼쪽 리스트와 오른쪽 리스트에 대해 재귀 호출 방식을 통해 리스트의 길이가 1이 될 때까지 각각 정렬을 수행한다.
시간 복잡도
퀵 정렬은 이름에서도 알 수 있듯이 가장 빠른 정렬 알고리즘으로 알려져 있다. 피벗값의 위치가 변경되어 리스트가 분할될 때마다 데이터의 개수가 절반으로 나뉘기 때문에 평균적으로 O(N logN)의 시간 복잡도를 갖는다. 다만, 데이터가 이미 정렬되어 있는 리스트에서 퀵 정렬은 O(N^2)의 시간 복잡도를 갖는다.
특징
• 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
• 병합 정렬과 더불어 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다. 가장 작은 데이터와 가장 큰 데이터의 범위가 모두 담길 수 있도록 리스트를 생성한다. 처음에는 해당 리스트의 모든 데이터를 0으로 초기화한다. 이후, 정렬하고자 하는 리스트의 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 결국 생성한 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록되고, 리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 정렬된 리스트를 얻을 수 있다.
시간 복잡도
앞에서부터 데이터를 하나씩 확인하며 리스트의 값을 1씩 증가시키고, 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복을 수행해야 하기 때문에 O(N + K)의 시간 복잡도를 갖는다.
공간 복잡도
데이터가 0과 999,999만 존재하는 리스트의 경우에, 크기가 1,000,000개가 되도록 새로운 리스트를 생성해야 한다는 문제점이 있다. 하지만 적절한 조건을 만족한다면 정렬해야 하는 데이터의 개수가 많을 때에도 효과적으로 사용할 수 있다. 평균적으로 계수 정렬의 공간 복잡도는 O(N + K)이다.
특징
• 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하다.
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효율적으로 사용할 수 있다.
• 현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 할 수 있다.
--
참고 도서
🙇🏻♂️ 나 동빈, 이것이 취업을 위한 코딩테스트다
