728x90

선택 정렬(Selection Sort)은 정렬되지 않은 데이터들에 대해
가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다
.

[ 10, 0, 97, -30, 5 ]

위 배열에 들어있는 숫자를 오름차순으로 정렬해보자.

Selection Sort 진행 과정

🎈선택 정렬 코드를 실행하면 위와 같은 과정으로 정렬이 진행된다.

가장 작은 값의 기준은 항상 맨 앞 index이다. 하지만, 정렬이 완료되는 순서도 가장 앞부터 완료된다.
이걸 고려했을 때, 가장 작은 값의 기준은 0, 1, 2, 3, ... 씩 증가한다고 생각하면 된다.

그렇게 나머지 오른쪽 값들과 반복 비교하여 가장 작은 값의 인덱스를 저장하고,
그 값이 첫 번째 기준값과 같은 것이 아니라면 서로 값을 교환해준다.

선택 정렬 수도 코드(Selection Sort Pseudo Code)
선택 정렬 최종 코드

🧨 위의 코드처럼 중첩 for loop을 이용하고, indexOfMin외부 for loop이 진행될 때마다 새로 설정해준다.
그리고 내부 for loop에서 반복 비교해주고, 가장 작은 값의 index를 얻어낸다.
최종적으로 처음에 초기화한 i인덱스와 같지 않은 지 확인하고, 같지 않다면 서로 값을 교환해준다.

if( indexOfMin !== i ) 조건문이 들어간 이유는, indexOfMin보다 작은 값을 찾지 못 했을 때
indexOfMin은 여전히 i값을 가지고 있을 것이기 때문에 그런 상황을 대비해주는 것이다.

버블 정렬과 비교했을 때, 여전히 시간 복잡도는 O(n^2)지만 이렇게 다른 방법으로 접근할 수도 있다.

728x90

버블 정렬(bubble sort)서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방이다.

[ 97, 5, 10, 0, -30 ]

위의 배열에 들어있는 숫자오름차순으로 정렬해보자.

Bubble Sort 진행 과정

🎈버블 정렬 코드를 실행하면 위와 같은 과정으로 진행 된다.

이해하기 쉽게 하기 위해서, 예시 배열 숫자에는 가장 큰 수를 맨 앞에 그리고 가장 작은 수를 맨 뒤에 넣어보았다.

첫번째 사이클에서,
이웃한 데이터를 비교해가며 index를 하나씩 증가해 나가기 때문에 가장 큰 수(97)는 맨 뒤에 자리할 수밖에 없다.
첫 번째 index부터 '앞자리 > 뒷자리'기준으로 비교하기 때문이다. 97보다 큰 수가 없다면 앞의 비교문은 언제나 참이다.

하지만, 가장 작은 수는 맨 뒤에 있기 때문에 한 칸밖에 이동하지 못 한 것을 볼 수 있다.
이 내용을 볼 때, 가장 작은 수가 맨 앞에 위치하기 위해서는 배열의 크기만큼 반복문이 반복되어야 한다는 것을 알 수 있다.
또한, 이제 마지막 index는 비교 대상이 아니라는 것을 알 수 있다. 끝 index는 이미 정렬이 끝났다. 
따라서, 다음 비교 사이클에서는 index를 하나 줄여 비교를 진행해야 한다.

위의 과정이 반복되는 것이 버블 정렬이다. 이 내용을 토대로 코드를 작성해보겠다.

버블 정렬 최종 코드

🧨위에 보이는 것처럼 for loop 중첩으로 버블 정렬을 해결할 수 있다.

앞서 말한 것처럼 외부 for loop에서는 배열의 길이만큼 반복해준다.
내부 for loop에서는 외부 for loop이 한 사이클 돌 때마다, 마지막 index는 정렬이 끝나므로
배열의 길이 - i 만큼을 범위로 지정해준다.
그리고 내부 for loop에서 if 조건문을 이용해 뒤에 숫자보다 앞의 숫자가 크면 교체(swap)해주면 된다.

지금까지 버블 정렬을 이용해서 숫자를 정렬하는 방법을 작성해봤다.
하지만, 버블 정렬O(n^2)만큼의 시간 복잡도(Runtime complexity)를 갖기 때문에 시간적으로 굉장히 안 좋은 방법이다. 
하지만, 코드를 구현하기에는 가장 쉬운 정렬 방법이다.

다음 글에서는 같은 시간 복잡도지만, 다른 정렬 방법인 선택 정렬(Selection Sort)를 작성해보겠다.

+ Recent posts