[2021 하계 모각코] 4차시

정렬 알고리즘

 

1. 선택 정렬

​

오름차순 정렬일 경우 제일 작은 값을 골라 차례 차례 제일 작은 인덱스부터 집어넣는다.

즉 현재 인덱스에서 최대 인덱스까지 값들 중에 최소값을 선택하여 현재 인덱스에 집어넣고 인덱스를 증가시킨 후 이과정을 반복한다.

​

내림차순 정렬일 경우 제일 작은 값을 고르는 것이 아닌 제일 큰 값을 고르면 된다.

​

​

2. 버블 정렬

​

현재 인덱스의 배열 값과 다음 인덱스의 배열 값을 비교해 오름차순, 내림차순 조건에 따라 조건에 부합하면 교화하는 식의 정렬이다.

오름차순 일경우 현재 인덱스와 다음 인덱스의 두 값을 비교해 오른쪽 값이 더 작을경우 교환한다. 이렇게 하면 처음 한번 실행했을 때 마지막 인덱스에 제일 큰값이 오게 되고 다음 턴에서는 마지막 인덱스를 제외하고 교환하면 된다.

​

​

3. 삽입 정렬

​

배열의 한 원소를 key값으로 가지고 있고 이 key를 알맞은 자리에 삽입하는 방식이다.

key값은 인덱스 1부터 시작하여 하나씩 증가되는데 이때 키값과 이전 인덱스의 원소들을 비교하여 key값을 이전 인덱스의 알맞은 자리에 삽입하는 것이다.

​

​

4. 합병 정렬

​

분할 정복 방식으로 설계된 알고리즘으로 분할정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 것이다.

하나의 배열을 연산을 하면서 두개의 배열로 계속 쪼갠 후에 1개의 원소를 가지게 되었을 때 정렬하여 합치면서 하나의 배열을 만드는 것이다.

​

​

5. 퀵정렬

​

분할 정복 방식으로 정렬을 수행하는데 피봇값을 기준으로 작은 값은 왼쪽, 큰값은 오른쪽으로 옮기는 방식이다. 이후 피봇값을제외한 구간에서 반복하는데 배열의 크기가 1이 됐을 때 정렬이 완성된다.

이때 피봇 기준 작은 값과 큰값은 배열의 양 끝에서 포인터를 이동시켜 옮겨야할 두 값을 교환하는 방식으로 이루어진다.

​

 

---

시간 복잡도

​

​

 

---

https://github.com/miraekwak/BOJ/blob/main/1026.py

GitHub - miraekwak/BOJ