안녕하세요, 여러분

SW마에스트로 서포터즈입니다!

벌써 9월이 된 지도

개강을 한 지도 4주가 되어가는데요.

오늘은 가벼운 주제이면서도 매번 헷갈리는 그 개념!

정렬 알고리즘에 대해 준비했습니다~!

먼저 가장 쉬운 선택 정렬에 대해 알아볼게요.

선택 정렬은 제자리 정렬 알고리즘으로,

정렬해야 하는 배열 외

추가 메모리가 필요하지 않은 정렬 방식이에요.

먼저 주어진 배열을 싹 훑어보면서 최솟값을 검색하고,

그 최솟값을 배열의 처음 값, 그러니까 맨 왼쪽 값과 바꿔요.

그리고 방금 찾은 최솟값을 제외한

배열에서 또 최솟값을 찾고,

두 번째 자리의 값과 바꾸고...

이 과정을 반복하는 거죠.

다음은 삽입 정렬이에요.

삽입 정렬은 카드 게임을 하면서 손으로 들고 있는

카드를 정리하는 방법과 비슷한 정렬 알고리즘으로,

맨 처음에는 두 번째 값을 골라서 첫 번째 값과 비교해요.

작으면 바꾸고, 아니면 놔둬요.

그리고 세 번째 값을 골라서 두 번째 값과 비교해요.

세 번째 값이 두 번째 값보다 작으면

첫 번째 값과 비교해서

첫 번째 값보다도 작으면 첫 번째 자리로,

첫번째 값보다는 크고 두 번째 값보다는 작으면

두 번째 자리로 넣어요.

정렬하려는 값을 하나 골라서 계속 왼쪽으로 이동하면서

알맞은 자리에 넣는다고 보면 돼요!

다음은 합병 정렬입니다. 병합 정렬이라고도 해요.

합병 정렬은 분할 정복 알고리즘의 하나로,

분할 정복이란 하나의 큰 문제를 여러 개의 작은 문제로 분리하여 해결하는 것을 말합니다.

같은 원리로 정렬하고자 하는 배열을

크기가 같은 둘로 쪼개서

그 작은 리스트들을 또 쪼개고 쪼개요.

그래서 길이가 1이 됐을 때

인접한 다른 리스트와 합치면서 정렬합니다.

정렬된 리스트를 또 다른 정렬된 리스트와 합치고,

이것을 계속 반복하면

최종적으로 원래 정렬하고자 했던

큰 리스트가 정렬되는 원리예요.

마지막 퀵 정렬은

합병 정렬과 같은 분할 정복 알고리즘으로

실제 과정도 유사하지만,

퀵 정렬은 리스트의 길이를

서로 다르게 나눈다는 차이가 있어요!

퀵 정렬에서는 먼저

피벗 이라는 (pivot) 기준값을 하나 정합니다.

그리고 피벗보다 작은 값은 전부 피벗의 왼쪽으로,

큰 값은 전부 오른쪽으로 보내요.

그리고 피벗을 기준으로 나눠진

왼쪽과 오른쪽의 리스트에서

각각의 새로운 피벗을 정하고 이 과정을 반복합니다.

오늘은 가볍게 정렬 알고리즘에 대해 알아봤어요.

매번 헷갈리는 개념인데 이번 포스팅을 통해

가볍지만 확실하게 복습하셨으면 좋겠네요.

다음에도 재미있고 알찬 소식으로 찾아오겠습니다~

SW마에스트로 서포터즈였습니다

감사합니다!