[삼성 알고리즘] 정렬 알고리즘(버블, 선택, 삽입, 병합, 퀵) 1

안녕하세요 이번 포스팅 내용은 알고리즘의 기본이자 언제나 중요한 자리를 차지하고있는 Sort 알고리즘에 대한 포스팅을 진행하겠습니다.

포스팅을 진행할 알고리즘은 Sort알고리즘 중에서도 가장 많이 알려져 있고 정보처리기사, 면접 등 여러 시험에서도 높은 출제율을 가지고 있는 버블, 삽입, 선택, 병합, 퀵 알고리즘을 진행하겠습니다.

 

1. 삽입 정렬

가장 먼저 삽입 정렬(Insert)에 대해서 진행하겠습니다.

먼저 처음 주어진 배열의 상태가 위와 같고 위 배열을 통해 삽입 정렬을 통한 오름차순 정렬과정을 보이겠습니다.

 

 

진행 1 과정은 위와 같습니다. 먼저 두번 째 인덱스인 2를 바탕으로 현재 인덱스보다 앞에 있는 숫자와 비교를 통해 자신이 들어갈 자리를 찾습니다. 가장 앞에있는 5와 비교를 통해 자신의 자리가 가장 앞임을 확인하고 자기 자신을 배열에서 빼줍니다. 그 후 5 값을 우측으로 밀어주고 처음에 5가 있었던 자리에 2를 삽입시켜줌으로써 정렬을 진행합니다.

 

진행 2 과정역시 세 번째 인덱스인 4를 기준으로 두 번째, 첫 번째 인덱스 순으로 비교를 진행합니다. 먼저 두 번째 인덱스 값이 5이므로 4와 비교 결과 4가 더 작으므로 세번 째인덱스에서 두 번 째 인덱스로 이동될 예정입니다. 다음으로 첫 번째 인덱스 2와 비교한 결과 2보다는 큰 값이므로 4의 자리는 두 번째 인덱스인 것을 확인할 수 있습니다. 데이터의 자리를 확인한 후 진행 1과 마찬가지로 4를 빼고 5를 이동 그리고 4를 두 번째 인덱스 자리에 삽입합니다.

진행 3의 경우는 네 번째 인덱스인 1을 바탕으로 비교를 진행합니다. 비교 결과 세 번째, 두 번째, 첫 번째 인덱스 모두 큰 것을 알 수 있고 맨 앞(첫 번째 인덱스) 자리가 1의 자리인 것을 알 수 있습니다. 자리를 찾은 뒤에는 앞서 본 것과 마찬가지로 2,4,5를 우측으로 밀고 1을 삽입시켜줍니다.

마지막으로 진행 4과정 입니다. 이번에는 마지막 인덱스인 7값을 기준으로 비교를 진행합니다. 하지만 이번에는 바로 앞 인덱스인 5와 비교결과 7이 더 큰 것을 확인할 수 있습니다. 이 때, 현재 기준이 되는 인덱스 앞의 인덱스는 모두 정렬이 되어있음을 가정하므로 더 이상 비교를 진행하지 않고 7은 이동하지 않음으로써 정렬을 마무리 할 수 있습니다.

 

삽입정렬의 진행과정은 다음과 같습니다. 삽입 정렬의 경우 최상의 경우(모두 정령이 되어있는 경우) N개의 데이터가 저장된 배열에 한해서 N 번의 비교만 진행하므로 O(N)의 좋은 성능을 가지고 있습니다. 하지만 최상의 경우가 아닌 경우 평균적으로 O(N^2)의 성능을 가지고 있습니다.

 

 

2. 버블 정렬

버블 정렬 역시 위와 같은 예시를 바탕으로 진행하겠습니다.

버블 정렬을 한 번 진행했을 때 결과는 위와 같습니다. 버블 정렬의 경우 N개의 데이터가 있을 때 N-1번의 비교를 진행합니다. 비교 순서는 보통 앞에서부터 진행되며 위와 같이 처음 5와 2를 비교해서 자리를 바꿔주고 또 5와 4를 비교해서 자리를 변경 그 후 5와 1을 비교해서 자리를 변경 5와 7을 비교해서 자리 유지식으로 정렬이 진행됩니다.

 

진행 2역시 진행 1과 같습니다. 처음부터 비교를 두 개씩 순서대로 진행합니다. 마치 거품이 번져나가듯 계속 비교 및 교환을 진행하면서 정렬하는 방법입니다.

진행 3을 마치게 되면 정상적으로 정렬이 모두 된 것을 확인할 수 있습니다. 근데 보통 간단하게 이중 for문으로 코드를 작성하게 된다면 최악의 경우를 고려해서 작성하기 때문에 아래와 같이 정렬이 된 후에도 진행 4 과정까지를 한 번 진행합니다.

정렬 후 종료 부문이 없이 이중 for문으로만 버블 정렬을 구현한 경우 다음과 같이 최악의 경우가 아닌 경우 비교 연산이 추가로 발생할 수 있습니다.

 

버블정렬의 경우 N개의 데이터가 있는 배열의 정렬을 진행할 때, 연산 1번마다 N-1번의 비교연산이 진행되며 비교연산은 N-1번 진행하므로

(N-1)*(N-1)로 O(N^2)의 성능을 보이게 됩니다.

 

 

3. 선택 정렬

다음으로는 선택정렬 입니다. 선택 정렬은 비교를 통해 비교 데이터들 중 가장 작은 값을 계속 뽑아나감으로써 정렬을 진행합니다.

선택 정렬 역시 위와 같은 예를 바탕으로 진행하겠습니다.

 

진행 과정은 위와 같습니다 먼저 처음 선택 정렬을 진행할 때는 N개의 데이터에 대해서 가장 작은 최솟값을 찾아내고 해당 값을 가장 왼쪽에 넣어 줍니다.

 

진행 2에서는 진행 1에서 결정된 값을 제외한 N-1개의 데이터에서 가장 작은 최솟값을 선택하고 해당 값을 2번째 인덱스 자리로 이동합니다.

 

진행 3,4 역시 각각 N-2, N-3 개의 데이터 중에서 최솟값을 선택하고 좌측으로 정렬을 진행합니다.

해당 과정을 통해서 정렬된 데이터를 얻을 수 있습니다.

 

선택 정렬의 경우 N개의 데이터에 대해서 최솟 값을 찾기위해 N번, N-1번, N-2번 ... 1번 까지 연산이 진행됩니다. 여기서 1+2+3+...+N-1+N번의 연산이 진행되므로 수열을 통해서 O(N^2)의 성능을 가짐을 알 수 있습니다.

 

포스팅의 내용이 길어져서 병합정렬과 퀵 정렬은 다음 포스팅에 진행하겠습니다!!

 

혹시나 틀린 부분은 언제든지 댓글로 지적해주세요~! ㅎㅎ

 

감사합니다.