[sw정글 1주차] 권정렬

Date: 2022.09.28 Updated: 2022.09.28

📚SW정글 1.7주차

(사진: 10cm의 권정열)내가 좋아하는 가수중 하나

정렬에 대해 이리저리 공부하고 느낀바를 정리 해 보도록 하겠다.

정렬 알고리즘

정렬이 무엇일까? 라고 물어보면 이미 모두가 머릿속에 알고있는 그것이기 때문에 넘어가도록 하겠다. 정렬에 대해 공부를 하면 끝도 없다고 한다. 정렬 하나만으로도 수십년동안 연구하는 사람들도 있고, 하나의 정렬 주제를 가지고 박사학위까지 도전하는 사람들도 있는 마당에…

무튼 나름 열심히 정렬의 핵심에 대해 접근하며 알게 된 바를 적어볼까 한다. 막상 공부를 하고 알고리즘 문제를 풀려고 하는데, 공부 내용이 무색하게 파이썬에서 sort() 하나만으로 모든 문제들이 풀리는 모습을 보고 약간의 허망함을 느꼈다. 일부러 그렇게 풀지 않도록 설계된 문제들이 있다고는 하지만, 기본적으로 정렬이 필요한 경우에 sort() 함수를 사용하는 방법이 최선의 방법이라는게 대다수의 의견이였다.(그래도!! CS의 근본인 정렬을 공부했으니!! 나중에 어딘가에 도움이 잘 될 것이다…)

🫧버블정렬

d0014632_0802074

거품이 보글보글 올라오는듯 한 모습을 보여주는 정렬 방법이다. 말 그대로 거품이다. 시간 복잡도도 아주 높다. 모두가 생각 해 낼법한 그 정렬방법이다. 배열의 맨 처음부터 끝가지 주욱~ 살펴보며, 비교하며 정렬해준다. ~~(교육용 정렬 알고리즘이다)~~

✨버블정렬 개선하기1

하지만 성능이 다소 구린 버블정렬일지라도 개선의 여지가 분명히 있다. 비교를 하며 교환을 한 횟수를 counting 한다. 만약 비교를 주~욱 한바퀴 돌았는데 교환횟수가 0이라면 이대로 정렬을 끝내도 된다.

✨버블정렬 개선하기2

두번 째 개선 방법으로는 마지막으로 교환된 위치를 표시하는 것이다. 마지막으로 교환 된 위치를 표시하고 그 뒤부터 스캔을(비교를 주~욱 한다는 뜻.. CS에서는 비교하는 과정 및 비교&교환하는 과정을 pass 라고 표현한다)한다. 교환이 이루어 졌을 때 마지막 교환 위치가 비교적 뒤쪽이라면, 버블정렬이 생각보다 빠르게 종료될 수 있다.

✨버블정렬 개선하기3

정렬이 거~의 완료된 배열에 대해 적용할법한 방법이다. 셰이커 정렬이라는 방법인데, 칵테일을 만들 때 앞뒤로 쉐킷쉐킷 하듯이, 버블정렬을 앞으로 뒤로 흔들어 주는 방법이다. 한쪽 방향으로 갈 때는, 매번 교환이 이루어 질 배열도 뒤에서 역으로 해줌으로써 한방에 정렬이 완료될 수도 있다.

이렇듯 버블정렬은 많이 부족한 친구이기에, 개선의 여지도 많고, 이를 통해서 ‘아~ 이렇게 해볼수도 있겠구나’라고 생각할 법 한 재미있는 거리들이 많이 있었다.

👉단순 선택 정렬

슥~스캔을 해서, pass하려고 하는 범위에서 가장 작은 수를 선택해서 해당 위치에 박제넣어주는 정렬이다. 말 그대로 단순히 선택한다음 넣어주는 정렬이다.(a.k.a straight selectoin) 넣다보면 동일한 값이여도 위치가 뒤죽박죽 바뀔 수 있어서 unstable하다. 동일한 숫자이더라도 메모리위치라는게 있는데 이는 무시된다. 딱히 나에게 배움을 주지 않는 정렬 방법이다.

👉단순 삽입 정렬

단순 삽입 정렬이다. 이녀석은 Straight Insertion이라고 한다. 위의 Straight selecton과 이름이 상당히 비슷하다. 하지만 가장 작은 수를 넣는게 아니다. 스캔할 범위의 첫번 째 수를, 적절한 위치에 꽂아주는 정렬이다. 위의 버블정렬, 단순선택정렬과 마찬가지로 시간복잡도는 O( n ² ) 이다. 단순 삽입 정렬도 엄청난 시간복잡도 때문에, 개선의 여지가 많이 있다. 그중 하나가 이진 삽입 정렬이다. 하지만 마찬가지로 시간복잡도는 O(n^2^)이다.

🚀셸 정렬

단순 삽입 정렬의 장점을 살리면서도 단점을 보완한 정렬이다.

일정 간격을 가지고 정렬을 해주는 모습이다. 위의 이미지는 5칸 간격이므로 ‘5-셸정렬’ 이다. 이러면 피차일반이지 않나 싶었는데 average case에서는 n² 에서 n^1.5로 줄어들긴 한다… 하지만 worst case에서는… 쩝 아래의 표를 참고하도록 하자

중간정리

위에서 언급된 정렬들이다. 개선을 하더라도 근본적인 부분의 변화가 없으므로 모두 n² 오래걸린다.

알고리즘	Worst
버블정렬	n²
선택정렬	n²
삽입정렬	n²
이진삽입정렬	n²
셸정렬	n²

Best case나 average case에서는 조금씩 다르지만, Worst case의 시간복잡도만 논하도록 하겠다.

(속도가)괜찮은 정렬들

아래의 정렬들은 단순 교육용 정렬들이 아니다. 실제로 빠르게 동작하는 정렬들이다.

🚀🚀🚀퀵 정렬

속도가 가장 빠르다고 하는 퀵정렬이다. 퀵정렬은 패스를 원하는 범위에서 피벗을 하나 설정할 수 있고, 피벗의 위치에 따라 정렬속도에 큰 차이가 생긴다.

1_AN0o2gSP3ZjYagmk0cbE5A

피벗의 위치를 아싸리 패스범위의 시작 혹은 끝으로 두는 경우도 있으며, 통상적으로는 패스시킬 범위의 가운데에 둔다. 범위 내에서 피벗의 위치를 랜덤으로 두네 마네, 특정 규칙을 가지고 피벗의 위치를 계속 움직이자는 등 다양한 의견으로 논문이 발표될 만큼, 이미 가장 빠른 정렬의 속도를 더욱이 높이고자 많은 사람들이 노력중이다.

quick sort

다음과 같이 가운데에 있는 피벗을 향해 달려올 때, pl > pr 일 때 조건을 끝내주어야한다.(pass과정을 마치고 다음 분할을 하러 가야한다.

여기서 문제!! 만약 가운데의 피봇위치에서 pl과 pr이 만나게 된다면?

교환을 한다.
교환하지 않는다.

정답은 1번 교환을 한다이다. 교환을 하지 않는다면 원소를 교환할 때 마다 pl과 pr이 같은 위치인지 체크를 해야하는데, 매번 If문을 통해 체크하는 비용보다 1번만 같은 원소를 교환하는 비용이 더 적게든다.

코드로 간단히 이해해 보자. 1번: 교환을 하는 경우

while pl <= pr:
#pl과 pr이 서로를 향해 달려오도록 만듬
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr += 1

2번: 교환을 하지 않는 경우

while pl <= pr:
#pl과 pr이 서로를 향해 달려오도록 만듬
if pl <= pr:
if not pl == pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr += 1

그렇다. 매번매번 일어나기도 힘들 상황 ~~(pl씨와 pr양이 약속장소 피벗나무 앞에서 아름답게 만나는 상황)~~ 을 위해 매번 if문으로 조건을 처리하는게 더욱 큰 비용을 야기시킨다.

👫병합 정렬

oMbHRV9

전부 다 찢어두고 원소를 하나씩 짜맞춰나간다. 오징어포마냥 찢어놓은 데이터들을 잠시 둘 임시공간이 필요하다. 따라서 외부정렬 방식이다. 위에서의 퀵정렬은 추가적인 데이터가 필요하지 않기 때문에 내부정렬이라고 볼 수 있다. 애니메이션을 보면, 뭔가 이루어지나 싶다가.. 어느순간 펑~ 정렬이 되어버린다

그럼 누가 더 빠를까?

거대한 데이터의 경우 병합정렬이 빠르고, 그렇지 않은 경우 퀵정렬이 더 빠르다고 한다. 어차피 큰 데이터를 효율적으로 정렬하기 위해 알고리즘들을 사용하므로 병합정렬이 짱일까? 또 그렇지는 않다. 대부분의 프로그램들은 짧은 시간동안 반복적으로 접근하는 데이터들 이다. 상황에 맞는 정렬 알고리즘들이 있겠지만 그래서 사람들은 퀵소트를 더 기억해준다. (이름부터 퀵소트가 더 멋있다 퀵… 오…)

시간복잡도 외에 정렬 알고리즘에서 고려될만한 부분들이 있다. 바로 Locality 이다. 왜 Locality가 정렬 알고리즘의 평가 기준이 될 수 있을까?

머지소트처럼 데이터가 계속 이동이 필요한 경우, 다른 캐쉬에 없는 페이지로 이동을 해야 하고 page cache hit 비율이 떨어지게 된다. 이는 결국 캐시가 가지고 있을만한 범위를 벗어나게 되고, 결국 physical memory에도 접근해야한다. 결국 위에서 말한 내부정렬의 진가가 나오는 순간이다.

따라서 일반적인상황에서 더욱 더 퀵소트를 찾게되는 이유이다. 정리하자면, 데이터들의 Locality를 높게 가져갈 수 있는 퀵소트가 캐쉬의 도움을 더 많이 받을 수 있고, 이는 퀵소트의 성능을 더욱 더 아름답게 만들어준다.

🏔힙 정렬

내생각에 가장 비운의 정렬이다. 힙하게(멋있게) 정렬한다는 뜻인 줄 알고, hip-sort로 알고있었는데.. Heap-Sort 이다. 일단 퀵소트보다 느리다. 퀵정렬 처럼 똑같이 O(N_logN)의 시간복잡도를 가져간다. 하지만 실제로 돌려보면 퀵정렬보다 느리다. 위에서 말한 Locality의 영향인것일까? 그리고 실제로 돌려보면 다른 정렬들에 비해서도 조금 느리며 안정성도 보장받지 못한다.

그래서 사람들이 큰 관심이 없다.

검색해도 정보가 별로 나오지 않는다. 가장 유용한 정보는 아래의 heap정렬의 이해를 도와주는 웃긴 동영상 뿐이였다.

그래도 사라지지 않는데에는 이유가 있다. 꽤나 빠르며, 최악의 경우가 아니라면 이론상 퀵소트보다 시간복잡도가 높다. O(N_logN)의 시간복잡도 알고리즘 중 가장 효율적이라고 볼 수 있다(실제로 그렇게 동작핟지는 않지만..)

그리고 굳이 장점을 조금 더 찾아보자면, 최대값과 최소값을 찾기 쉽다. max와 min을 구할 때는 O(1)의 시간복잡도를 가진다. 다른 장점들을 열심히 찾아보았지만.. 알아 볼 수록 뭔가 미안해지는 알고리즘이다.

😵도수 정렬

[ 1, 2, 99999999999, 3, 4, 5]

위의 데이터를 정렬하려면, 99999999999 이상의 배열크기를 가진 메모리가 추가적으로 필요하다. O(N)이라는 사기적인 time-complexity를 가지고 있지만 낭비되는 인덱스가 너무 많다.

⏰Tim sort

팀정렬? 이라고 부르려다가 어감이 이상해서 Tim sort로 적어두었다. 2002년 Tim Peters가 만든 정렬 알고리즘이며, 삽입정렬과 병합정렬의 장점을 모아서 만든 정렬이다. 실생활 데이터들의 특징을 고려해서 정렬을 만들었다고 한다. 아울러 병합정렬이 들어갔기 때문에 당연히 추가적인 메모리를 요구한다. 정렬들의 성능향상을 위해서 추가적인 메모리는 필수적인가 보다 싶다.

위에서 말한 이진삽입정렬(위로이동) 과 머지소트에 Galloping이라는 최적화 기법을 적용하였다. 2^x개 까지는 삽입정렬을 진행하고, 그 이후의 원소에 대해서는 가능한 덩어리를 크게 만들어 내는데 이를 Run 이라고 한다. run이 3연속으로 병합되었다? => 질주모드(Galloping mode), run이 연속적으로 병합되지 않으면? => 일반모드(One pair at a time mode)로 전환되는데 질주모드에서는 2^k 을 뛰어넘으며 삽입정렬의 대소비교를 이루어 나간다고 한다.

현재 Python, Java, Android, chrome, swift 등 다양한 곳에서 표준 정렬 알고리즘으로 채택되었다고 한다. 어쩌면 우리가 가장 많이 사용하고 있을 Tim sort 알고리즘은 네이버 D2 블로그에 더욱 정확히 잘 설명되어 있다.

😵배우면서 깨달은 내용을 정리해 보았습니다. 오개념을 아래 댓글에 달아주시면 감사하겠습니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

Sunny Yoon