[Algorithm & Data Structure] Sorting Algorithm

/ "Normad Coder의 알고리즘과 데이터 구조 강의" 듣는 중//

​

• Big O는 알고리즘의 퍼포먼스를 이해하기 쉽게 효율적으로 작성하는 방법
• but, 모든 알고리즘을 완벽하게 설명 x
• 같은 Big O를 갖더라도 퍼포먼스는 매우 다를 수 있음.

​

sorting

• 정렬: 뭔가를 정리하는 것
• 이진 검색처럼 빠른 검색을 하려면 무조건 배열을 "정렬"해야 함
• buble, seleciton, insertion이 가장 빠른 정렬은 아니지만 일단 쉬운 것들임.
• 실제로 사람들이 정렬하는 방법과 유사함. 시간 복잡도 계산도 쉬움

​

​

1. Buble Sort 버블 정렬

• 사실 딱히 좋은 알고리즘이 아니라서 많이 사용 x
• 근데 이해하기 좋음
• 맨 앞에 2개의 아이템을 선택하고, 그 2개 값을 비교함. 만약에 L, R을 비교해서 L > R이면 두 개를 교환함swap
• 오른쪽으로 이동하면서 계속 반복.
• 만약에, L < R 작으면 그대로 두고 다음 두 아이템으로 넘어감.
• 아... 이게 첫 사이클 끝나도, 정렬이 다 안됐으면, 다시 앞으로 와서 제일 큰 수가 마지막으로 갈 때까지 사이클 반복함.

출처: Normad Coder 영상 캡쳐

 

 

출처: Normad Coder 영상 캡쳐

 

• 비교하고 스와핑하는 것의 반복.
• 너무....비효율적
• 비교: N-1 번 해야 함. 2개씩 다해야 하니깐,, 사이클마다... N-2... 이런 식으로 계속
• 최악의 경우에는 전부다 바꿔야 함. N번 스왑.. --> 작은 수에서 큰 수로 정렬을 하고 싶은데 반대면.. 머리 아픔
• so, 시간 복잡도는 O(n^2)
• --> 안 좋아......

​

​

2. Selection Sort 선택 정렬

• 전체 아이템 중 가장 작은 아이템을 찾고, 그 위치를 변수에 저장함.
• 순서상 가장 낮은(low; 가장 왼쪽) 것부터 시작해서 비교하다가 작은 수 나오면 변수에 저장하고,
• 계속 비교하다가 제일 작은 아이템(예, 1)이 나오면 위치를 저장하고 사이클을 끝냄.

출처: Normad Coder 영상 캡쳐

• 확인하는 동안에 딱히 스왑은 하지 x

출처: Normad Coder 영상 캡쳐

• 위치가 전부 확인되면 가장 작은 아이템을 맨 아래(왼쪽)의 아이템과 스왑함.(예, 1 <-> 5)
• 1은 이미 정렬이 되었기 때문에 제외하고 그 다음 것부터 다시 가장 작은 숫자를 찾음.

 

출처: Normad Coder 영상 캡쳐

• 다시 2부터 쭉 찾는데 그대로 맞으니깐, swap 없이 쭉 6부터 다시 찾고, 3이랑 스왑하고 계속 반복.

 

출처: Normad Coder 영상 캡쳐

• 하나하나 다 비교하니깐 버블 처럼 비교는 N-1임.
• 근데 버블과 다르게 최악의 경우 N번의 스왑은 x
• 즉, 비교는 다 해도, 제일 작은 아이템을 찾고, 해당 위치에 싸이클마다 단 1번만 스왑하면 됌.
• 버블보다 훨씬 나음.
• but, 시간복잡도는 O(n^2)로 똑같음.

​

3. Insertion Sort 삽입 정렬

• 동일한 배열로 계속 하는 즁.
• 인덱스 1에서 시작헤서 왼쪽에 '2'보다 큰 숫자가 있는 지 확인함.

출처: Normad Coder 영상 캡쳐

• 5가 더 크면 오른쪽으로 밀고, 바로 2번째 싸이클 시작.

출처: Normad Coder 영상 캡쳐

• 오른쪽이 더 크면 냅두고 다음 사이클 진행 so, 3번째 싸이클 시작은 3이고, 6이랑 비교.
• 6 <-> 3 바뀌면, 다시 3이랑 5비교 5가 크니깐 5를 오른쪽으로 밀기. 그럼, 2가 3보다 크지 않기 때문에 올바른 위치임
• 다시 4번째 사이클 1에서 시작함. 1은 아래 끝까지 쭉쭉 비교하면서 내려감.

출처: Normad Coder 영상 캡쳐

• 마지막 사이클을 4로 똑같이 하면 됌.
• 선택 정렬은 전체 모든 아이템을 스캔하지만, 삽입 정렬은 필요한 아이템만 스캔하기 떄문에 삽입정렬이 젤 빠름.
• but, 삽입 > 선택 > 버블 순서로 속도가 빠르지만, 시간 복잡도는 전부다 O(n^2)
• 이 경우에 빅오가 잘못되었다고 하기보단, 최악의 시나리오가 아닌 평균 시나리오를 확인해야 함.
• coz, worst와 best는 자주 발생하지 않고, 대개 평균에 속하기 때문에
• 이를 감안하면,

출처: Normad Coder 영상 캡쳐

 

• 삽입은 베스트면 선형이랑 같으나, 평균은 결국 이차임..

출처: Normad Coder 영상 캡쳐

• so, 디테일들을 잘 살펴야 함.
• 동일한 시간복잡도를 가졌더라도, 매우 다르게 나타날 수 있기에.
• 삽입, 선택 정렬은 작은 DB 기준에서는 훌륭한 알고리즘임.
• 데이터가 커지면 좀 느려지겠지만,,

​

​

==> 얘네는 외울 필요는 없음, 걍 정렬을 이해하기 위한 용도이고, 최근에 많이 쓰는 정렬들은 X

• 왜 정렬이 복잡하고, 더 좋은 솔루션이 필요한 지 이해할 수 있게 돕는 것.