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

수강한 강의
Chapter 12 기본 정렬 알고리즘
- 버블 정렬

학습 후기
강의에서 자료구조 강의를 지나 알고리즘 강의를 시작하고부터 직접 구현해보고 이해하는데 시간이 오래 걸려 진도가 조금씩 더딘 거 같다. 그래도 이번에는 진짜! 꼭! 제대로 코딩 테스트를 통과하고 싶기 때문에 제대로 이해하고 구현하고 넘어가려고 한다.

알고리즘 연습 방법
이번 강의 시작 부분에는 알고리즘 연습 방법을 알려주셨는데 평소 알고리즘 공부할 때는 그냥 프로그래머스나 백준과 같은 알고리즘 사이트에서 무작정 문제만 푸는 식으로 공부를 했다. 하지만 강의에서는 바로 문제를 풀지 말고 문제를 읽고 간단한 경우를 문장으로 적고 코드화 하기 위한 방법을 생각하고 코드로 구현하고 전체 코드로 어떻게 구현될지 적은 다음에 코드로 옮기라고 알려주었다.

버블 정렬
정렬이란 데이터를 순서대로 나열하는 것이다. 여러 알고리즘 문제에서 정렬은 필요하며 어떤 정렬이 어떻게 구현되었느냐도 어느 정도 학습이 필요하다.
버블 정렬은 두 수를 비교하여 앞의 데이터가 뒤의 데이터보다 크면 큰 수를 뒤로 넘기고 처음부터 끝까지 반복하여 제일 뒤에서부터 큰 순서로 정렬되는 알고리즘이다. 정렬되는 데이터를 시각적으로 보면 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고 한다.

아래 페이지에서 여러 정렬 알고리즘이 정렬하는걸 시각적으로 볼 수 있다.
https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

위키피디아에서 가져온 버블 정렬에 대한 예시이다.
55 07 78 12 42 초기값[파란색은 sorting]
07 55 78 12 42 첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78 두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78 세 번째 패스(pass)
07 12 42 55 78 네 번째 패스(pass)
07 12 42 55 78 다섯 번째 패스(pass)
07 12 42 55 78 정렬 끝

Bubble Sort example

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전

버블 정렬 알고리즘의 복잡도는 O(n^2)이고,
전부 다 정렬이 되어 있을 때(최선 일 때)는 O(n)이다.
구현 코드가 이중 for문으로 시간 복잡도가 O(n^2)이다. 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다.

수강 인증샷

https://bit.ly/37BpXiC

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

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