정렬과 탐색

 

여러 가지 정렬 알고리즘의 차이점을 이해하고,

 

해당 상황에서 어떤 알고리즘이 어울릴지 살펴보자

 

 

 

예를 들어 Cat이라는 객체로 이루어진 아주 크기가 큰 배열이 있다고 하자

 

이 배열에 담긴 객체들을 나이순으로 정렬하라고 했을 때 어떤 알고리즘을 사용해야 할까?

 

 

 

여기서 알 수 있는 2가지는

 

1. 배열의 크기가 크므로 효율성이 매우 중요하다.

 

2. 나이순으로 정렬하는 것이므로 그 값의 범위가 좁다는 것을 알 수 있다.

 

 

 

다양한 정렬 알고리즘들을 살펴봤을 때 버킷 정렬 혹은 기수 정렬이 가장 적합하리라는 것을 눈치챌 수 있다.

 

각 버킷의 크기를 1년으로 설정하면 O(n)에 정렬할 수 있다.

 

 

 

 

<자주 사용되는 정렬 알고리즘>

 

자주 사용되는 정렬 알고리즘을 알아두면 문제풀이 능력을 크게 향상할 수 있다.

 

 

1. 버블 정렬 

평균 및 최악 실행시간 : O(n^2), 메모리: O(1)

출처: wikibooks.org

버블 정렬은 배열의 첫 원소부터 순차적으로 진행하며

 

현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복한다.

 

이런 식으로 배열을 계속 살펴보면서 완전히 정렬된 상태가 될 때까지 반복한다

 

실제 데이터에서 본다면 이런 방식이다.

출처: wikipedia.org

 

 

 

2. 선택 정렬

평균 및 최악 실행시간: O(n^2), 메모리 : O(1)

출처-wikipedia.org

배열을 선형 탐색하며 가장 작은 원소를 배열 맨 앞으로 보낸다 ( 맨 앞에 있던 원소와 자리를 바꾼다)

 

그다음 두 번째로 작은 원소를 찾은 뒤 앞으로 보내준다.

 

이 작업을 모든 원소가 정렬될 때까지 반복한다.

 

 

 

3. 병합 정렬★

평균 및 최악 실행시간: O(n log n), 메모리: 상황에 따라 다름

출처-https://velog.io/@haero_kim/%EC%95%88%EC%A0%95%EC%A0%81-%EA%B7%B8-%EC%9E%90%EC%B2%B4-Merge-Sort

병합 정렬(merge sort)은 배열을 절반씩 나누어 각각을 정렬한 다음

 

이 둘을 합하여 다시 정렬하는 방법이다.

 

나눈 절반을 정렬할 때도 같은 알고리즘이 사용되고 결국에는 원소 한 개짜리 배열 두 개를 병합하게 된다.

 

병합할 때 예비공간을 추가로 사용하기 때문에 병합 정렬의 공간 복잡도는 O(n)이다.

 

이 알고리즘에서는 병합을 처리하는 것이 가장 복잡하다.

 

병합 작업을 수행하는 메서드는 병합 대상이 되는 배열의 두 부분을 임시 배열(helper)에 복사하고, 

 

왼쪽 절반의 시작 지점(helperLeft)과 오른쪽 절반의 시작 지점(helperRight)을 추적한다.

 

그런 다음 helper를 순회하면서 두 배열에서 더 작은 값의 원소를 꺼내어 원래 배열에  복사해 넣는다

 

두 배열 중 한 배열에 대한 순회가 끝난 경우에는 다른 배열의 남은 부분을 원래 배열에 남김없이 복사해 넣고 작업을 마친다.

 

 

 

4. 퀵 정렬★ 

실행시간: 평균 O(n log n) , 최악 O(n^2), 메모리" O(log n)

출처-https://latte-is-horse.tistory.com/197

퀵 정렬은 무작위로 선정된 한 원소를 사용하여 배열을 분할하는데

 

선정된 원소보다 작은 원소들은 앞에 큰 원소들은 뒤로 보낸다.

 

배열 분할 작업은 연속된 스왑 연산을 통해 효율적으로 수행된다.

 

배열과 그 부분 배열을 반복적으로 분할해 나가면 결국에 배열은 정렬된 상태에 도달한다

 

하지만 배열 분할에 사용되는 원소가 중간값 , 적어도 중간값에 가까운 값이 되리라는 보장이 없기 때문에

 

정렬 알고리즘이 느리게 동작할 수도 있다.

 

그래서 최악의 경우엔 수행 시간이 O(n^2)이 될 수 있다.

 

 

 

5. 기수 정렬(radix sort)★ 

실행시간 O(kn)

 

1단계

출처-gifsoup

2단계

출처-gifsoup

기수 정렬은 버킷 정렬 응용 버전이다.

 

데이터가 정수처럼 유한한 비트로 구성되어있는 경우에 사용된다.

 

기수 정렬은 각 자릿수를 순회해나가면서 각 자리의 값에 따라 그룹을 나눈다

 

가령 정수 배열이 주어졌다고 하면 처음에는 첫 번째 자릿수를 기준으로 정렬한다.

 

따라서 첫 자릿수가 0인 수들은 같은 그룹에 속한다.

 

그런 다음 각 그룹마다 두 번째 자릿수를 기준으로 다시 정렬을 수행한다.

 

이 작업을 배열 전체가 정렬될 때까지 모든 자릿수에 대해 반복한다

 

비교 연산을 사용하는 정렬 알고리즘은 평균적으로 O(n log n) 보다 나은 성능을 보일 수 없으나

 

기수 정렬의 수행 시간은 O(Kn)이 된다. 여기서 n은 정렬 대상 원소의 개수이고 k는 자릿수의 개수이다.