정렬 알고리즘 (삽입, 선택, 버블, 병합)

오래전에 정처기 공부할때 정리했던것이다. 

Sort 알고리즘

---

 

1. 삽입 정렬

 

5 2 4 1 7

 

현재 인덱스보다 앞에 있는 숫자와 비교를 통해 자신이 들어갈 자리를 찾는다.

 

진행 1 결과 25417 (52417에서 2를 기준으로 5와 자리 바꿈, 앞에 있는 숫자와 비교)

진행 2 결과 24517 (25417에서 4를 기준으로 5번과 자리 바꿈)

진행 3 결과 12457 (24517에서 1를 기준으로 245 모두 우측으로 넣는다.)

...

 

최상의 경우 0(N) 평균적으로 0(N^2)

---

2. 선택 정렬

 

5 2 4 1 7

 

비교를 통해 비교 데이터들 중 가장 작은 값을 뽑아나감으로 정렬

여기서 헷갈릴만한건..작은값을 앞으로 밀어 넣는것이 아닌 자리 교체를 한다는 것이다

 

진행 1 결과 15247 (52417에서 가장 작은 수인 1를 선택해서 가장 왼쪽에 넣음)

진행 2 결과 12547(15247에서 가장 작은 수인 2를 선택해서 0번째 제외해서 가장 왼쪽에 넣음)

진행 3 결과 12457 (12547에서 가장 작은 수인 4를 선택해서 1번째 제외해서 가장 왼쪽에)

진행 4 결과 12....

 

0(N^2)의 성능

---

3. 버블 정렬

 

52417

N개의 데이터가 있을때 n-1번의 비교를 통해 진행함

진행 1 결과 24157 (52417에서 옆에 있는 애들끼리 비교해서 바꿔줌)

진행 2 결과 21457(옆에 있는 애들끼리 비교해서 바꿔줌)

진행 3 결과 12457

진행 4 결과 12457

 

0(N^2)의 성능

---

4. 병합 정렬

 

n개의 데이터를 이분법을 통해 n/2개로 쪼개고 그 n/2개를 또 n/4의 4개로 쪼갠다.

합칠때 데이터의 크기를 비교하여 합치는 과정으로 정렬함

O(Nlog^2N)을 가지는 특징이 있음

 

단순(구현 간단)하지만 비효율적인 방법
삽입 정렬, 선택 정렬, 버블 정렬
복잡하지만 효율적인 방법
퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html