파이썬으로 자료구조, 알고리즘 공부하기! 버블 정렬(bubble sort), 쉘 정렬(shell sort)

이번 포스팅은 파이썬으로 자료구조, 알고리즘 공부하기 쉘 정렬(shell sort)과 버블 정렬(bubble sort)에 대해서 정리합니다.

여러가지 정렬 알고리즘이 있습니다. 지난 포스팅에선 삽입 정렬, 선택 정렬에 대해서 보았는데요

기본적인 정렬 중 버블 정렬이라는 것이 있습니다!

버블 정렬은 말 그대로 거품처럼 뽀글뽀글 올라가며 정렬을 하는데요

 

 

예시를 들면 이렇게 진행됩니다.

처음부터 하나씩 비교를 하면서 큰 것을 뒤쪽으로 몰아넣죠. 그리고 fix 시킵니다. 그리고 그 다음 루틴에서 또 돌고.. 이렇게 진행합니다.

바로 파이썬 코드로 봅시다

 

 

핵심은 def bubble_sort입니다. 정렬되지 않은 list를 입력 받습니다.

2개의 for문을 돌면서 진행합니다. 맨 처음 for문은 len - 1 범위로 진행하고 두 번째 for문은 1번째 인덱스부터 len - start_index(겉의 for문) 을 돌면서 for 루틴마다 마지막을 fix 시키면서 진행합니다

그리고 만약 index - 1 값이 index 보다 크다면 서로 값을 바꿔줍니다. 이렇게 진행됩니다.

 

 

진행 결과는 위와 같습니다. 마치 거품 처럼 올라가며 정렬한다고 해서 버블 정렬이라고 부릅니다!

다음은 쉘 정렬입니다. 쉘 정렬은 삽입 정렬을 개선한 방법입니다. 삽입 정렬은 계산되지 않은 배열에 대해서 계산량이 많이 드니까 이것을 좀 개선한 방법인데요. 아래와 같이 예시를 들 수 있습니다.

 

초기 상태 [5, 7, 6, 4, 1, 2, 3]이 있다고 가정합니다. 그러면 먼저 간격을 3으로 하면 2개의 리스트가 나옵니다! 이것이 sublist인데요. 이 sublist 별로 정렬을 하고 간격을 줄여줍니다.

그러면 간격 2로 되죠? 간격을 2로 하면 또 다시 sublist가 2개가 나옵니다

 

 

그러면 간격 2로 한 sublist를 또 정렬합니다.

그리고 마지막으로 간격을 1로하여 다시 삽입 정렬을 진행하면 정렬이 완료되는 것이죠!

바로 파이썬 코드로 쉘(shell) 정렬을 봅니다!

 

 

def shellSort는 껍대기고 gapInsertSort가 핵심 기능입니다. shellSort에서는 리스트를 입력으로 받고 interval 값을 줍니다. 먼저 len(list) // 2를 해서 절반으로 값을 넘겼네요. 그래서 처음에는 길이가 20인 배열 기준으로 10만큼 간격을 두며 배열 정렬을 합니다.

처음 들어가면 startposition은 0이 됩니다. 그리고 그 다음엔 startposition이 1이 되겠죠. 

for문을 들어가면 startposition부터 배열의 길이만큼 진행을 하는데 간격이 10입니다. position은 index 값을 받습니다. 처음은 0이 되겠죠. 그리고 현재 값은 0번째 인덱스가 됩니다.

그리고 while문을 도는데 position이 interval보다 크고 해당 간격에 있는 값이 현재 값보다 크면 그 값을 바꿔주는 방식으로 진행됩니다.

이렇게 간격만큼 진행되는데요. 0-10, 1-11, 2-12.. 이렇게 진행되고 끝이 납니다.

그리고 다시 한 번 gap을 //2 해서 또 진행합니다. 그러면 gap이 10에서 5만큼 감소 되고 똑같이 진행되겠죠!

그래서 아래와 같이 진행됨을 볼 수 있습니다.

 

 

간격은 10이고 처음 포지션은 0입니다. 간격이 10이기 때문에 다음 포지션은 10이 되구요. 그 다음 로직으로 인해 포지션은 다시 -=10이 되어 1이 됩니다. 이렇게 처음은 간격이 10을 기준으로 삽입 정렬을 합니다.

 

 

간격이 10 기준으로 정렬이 끝나면 이제 5를 기준으로 정렬을 합니다 (//2) 이렇게 계속 반복합니다!

 

 

최종적으로 간격이 1이됩니다. 1인 상태에서 삽입 정렬을 진행해서

 

정렬이 마무리 됩니다!

여기까지 파이썬을 활용한 버블 정렬(bubble sort)과 쉘 정렬(shell sort)을 알아보았습니다