지난 글에서 검색 알고리즘을 알아봤습니다.
서랍을 예시로 들면서 서랍 안에 내용물이 정리되어 있다면?
정리되어 있지 않다면?으로 나눠서 문제를 해결해봤습니다.
그렇다면 정렬은 어떤 방식으로 수행될까요?
버블 정렬
버블 정렬은 정렬 알고리즘 중 하나입니다.
버블 정렬의 개념부터 먼저 말하자면
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 인덱스를 변경하는 방식입니다.
다음과 같은 리스트를 예로 들어보겠습니다.
a라는 리스트에 담긴 값은 순서대로
4 3 1 5 2
입니다.
이 값을 버블 정렬의 개념을 이용해서 오름차순으로 정렬해볼까요?
일단 첫 두자리를 비교합니다.
4 3 1 5 2
첫 번째 숫자가 두 번째 숫자보다 크기 때문에 두 숫자의 위치를 변경합니다.
3 4 1 5 2
자 이제 다음 두 수를 비교해봅니다.
4는 1보다 크기 때문에 두 숫자의 위치를 변경합니다.
3 1 4 5 2
자 이제 다시 다음 두 수입니다.
4는 5보다 작기 때문에 두 수의 위치는 변경하지 않습니다.
3 1 4 5 2
이제 마지막으로 5와 2를 비교합니다.
5는 2보다 크기 때문에 두 수의 위치를 변경해줘야 합니다.
3 1 4 2 5
자 그럼 우리가 원하는 답이 나왔나요?
아직 정답은 아니지만 처음 주어진
[4 3 1 5 2]에 비하면 정답에 가까운 형태가 됐습니다.
방금 수행한 과정을 더 이상 위치 변경이 되지 않을 때까지 정렬하는 것
이것이 바로 버블 정렬입니다.
이 과정을 파이썬 코드로 한 번 나타내 보겠습니다.
실행 결과는 다음과 같습니다.
버블 정렬의 소요 상한 시간은 O(n^2)입니다.
선택 정렬
이번엔 다른 정렬인 선택 정렬을 알아보겠습니다.
선택 정렬은 우선 배열 안에서 가장 작은 수를 찾습니다.
위에 선언했던 리스트를 다시 가져와 보겠습니다.
4 3 1 5 2
자 우선 첫 번째 숫자가 제일 작은 수로 기억됩니다.
그다음으로 넘어가서 숫자를 봅니다.
3이네요.
4보다 작으니 이제 제일 작은 수는 3입니다.
4 3 1 5 2
또다시 다음 숫자를 확인해보겠습니다.
이번에는 1이네요.
3보다 작으니 이제 제일 작은 숫자입니다.
4 3 1 5 2
이제 다음 두 숫자를 순차적으로 비교해도 최종적으로는 1이 가장 작은 숫자입니다.
그렇다면 이제 가장 작은 수를 찾은 셈입니다.
이제 정렬을 하려면 어떻게 할까요?
오름차순 정렬이라고 가정할 때
가장 간단한 방식은 아마 첫 번째 위치와 찾은 숫자의 위치를 변경하는 것일 겁니다.
이러한 방식을 선택 정렬이라고 합니다.
설명한 과정을 파이썬을 이용해 확인해보겠습니다.
위와 같은 코드를 실행하면
선택 정렬이 일어나는 과정을 확인할 수 있습니다.
결과는 다음과 같습니다.
처음에 1과 4의 위치가 바뀌고,
그다음으로는 2와 3의 위치가 바뀝니다.
또 4와 3의 위치가 바뀌고
최종적으로는 4와 5의 위치가 바뀌면서 정렬이 완료되는 것을 확인할 수 있습니다.
선택 정렬의 소요 상한 시간은 버블 정렬과 마찬가지로 O(n^2)입니다.
출처 : 네이버 edwith, 부스트코스 [모두를 위한 컴퓨터 과학]
'내가 공부하려고 올리는 > 알고리즘' 카테고리의 다른 글
백준 구현 알고리즘 - 11723번(파이썬) (0) | 2022.05.11 |
---|---|
백준 알고리즘 - 그리디 알고리즘(1931번/1026번/1541번/2217번/13305번/10610번) (0) | 2022.04.25 |
모두를 위한 컴퓨터 과학(CS50) - 검색 알고리즘 (0) | 2022.04.21 |
파이썬 - 리스트/튜플/사전/집 자료형 (0) | 2022.04.20 |
[코드업] 기초 100 - Python(파이썬) 리뷰 (0) | 2022.04.20 |
댓글