코딩테스트 - 패스트캠퍼스 챌린지 10일차

수강한 강의
Chapter 12 기본 정렬 알고리즘
- 선택 정렬
- 삽입 정렬

학습 후기
선택 정렬
여러 데이터들을 순회하면서 가장 작은 수를 선택하여 앞쪽으로 보내면서 정렬하는 알고리즘이다.

선택정렬

선택 정렬 이미지 출처: https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전

아래의 순서에 따라 선택 정렬 알고리즘이 진행된다.
1. 리스트 데이터 중 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
장점: 구현이 비교적 간단하다.

간단한 정렬 예시
01. [3, 5, 1, 2, 4, 6] - 최솟값 3
02. [3, 5, 1, 2, 4, 6] - 최솟값 1
03. [1, 5, 3, 2, 4, 6] - 3, 1 swap
04. [1, 5, 3, 2, 4, 6] - 최솟값 5
05. [1, 5, 3, 2, 4, 6] - 최솟값 3
06. [1, 5, 3, 2, 4, 6] - 최솟값 2
07. [1, 2, 3, 5, 4, 6] - 5, 2 swap
08. [1, 2, 3, 5, 4, 6] - 최솟값 3 이후 데이터들 다 3보다 커서 위치 변경 없음.
09. [1, 2, 3, 5, 4, 6] - 최솟값 5
10. [1, 2, 3, 5, 4, 6] - 최솟값 4
11. [1, 2, 3, 4, 5, 6] - 5, 4 swap
12. [1, 2, 3, 4, 5, 6] - 최솟값 5 이후 데이터들 다 5보다 커서 위치 변경 없음.
13. [1, 2, 3, 4, 5, 6] - 최솟값 6 이후 데이터 없음.

선택 정렬 알고리즘 복잡도
중첩 for문의 사용으로 시간 복잡도는 O(N^2)이다.

삽입 정렬
리스트의 데이터들을 순회하며 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다.

삽입 정렬

아래와 같은 순서에 따라 삽입 정렬 알고리즘이 진행된다.
1. 리스트 데이터 중 2번째 값부터 시작한다.
2. 자기 위치의 앞의 데이터들과 비교하여 자기보다 크면 뒤로 민다.
3. 자신보다 작은 데이터가 나올 때까지 비교하며, 자신보다 작은 데이터를 찾으면 그 데이터 바로 뒤에 1에서 선택한 데이터를 넣는다.
4. 모든 데이터를 같은 방법으로 순회한다.
장점: 구현이 간단하다.
단점: 배열이 길어질수록 효율이 떨어진다.

삽입 정렬 알고리즘 복잡도
선택 정렬과 마찬가지로 중첩 for문이 사용되며 시간 복잡도는 O(N^2)이다.

삽입 정렬을 끝으로 기본 정렬 알고리즘 강의가 끝났다. 이후에 고급 정렬 알고리즘에서는 병합 정렬과 퀵 정렬을 배우게 된다. 기본 정렬 알고리즘은 구현하기 쉽다고 하니 여러 번 직접 작성해보며 바로바로 짤 수 있도록 익혀놓아야겠다.

수강 인증샷

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.