알고리즘/정렬(Sorting) (3) 썸네일형 리스트형 [알고리즘] 퀵 정렬(Quick Sort) - 코딩 밥상 퀵 정렬 이란? 이름 그대로 '빠른 정렬'이라고 할 만큼 앞서 배운 버블,삽입 정렬보다 월등히 좋은 성능을 갖습니다. '분할 정복'에 바탕을 둔 알고리즘으로서 동작을 한마디로 정리하면 기준 요소 선정 및 분할의 반복입니다. 기준이 될 요소를 임의로 선정하고 기준 보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 옮김 왼쪽 그룹과 오른쪽 그룹을 분할하여 각 그룹에 대해 1번 과정을 수행 그룹의 크기가 1 이하여서 더 이상 분할 할 수 없을 때까지 1번과 2번 과정을 반복 예를들어 5 1 6 4 8 3 7 9 2 을 오름차순으로 퀵 정렬 한다면, 5를 기준) 5 1 6 4 8 3 7 9 2 -> 1 4 3 2 5 6 8 7 9 1을 기준) 1 4 3 2 5 6 8 7 9 -> 1 4 3 2 5 6 8 7 9 왼.. [알고리즘] 삽입 정렬(Insertion Sort) - 코딩밥상 삽입 정렬이란? 삽입 정렬은 책장에 꽂힌 책을 정리하는 과정과 비슷합니다. 예를들어 시리즈 만화를 순서에 맞게 정리하자고 생각해 봅시다. 일단 책장의 왼쪽부터 오른쪽 방향으로 각 권이 옳은 순서로 꽂혀 있는지 확인하고, 잘못된 위치에 꽂혀 있는 책은 뽑아서 올바른 위치에 삽입해나가면 됩니다. 즉 삽입 정렬은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 요소를 찾고, 그 요소를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘입니다. 범위는 첫 2개 요소로 시작하며 알고리즘 수행을 반복하면서 1씩 증가하고 최대 '자료구조의 크기 - 1'까지 수행한다. 범위 마지막에 있는 요소가 정렬 범위 안에서 가장 큰 값을 갖는지 점검하고, 가장 큰 값이 맞으면 그대로 두고 그렇지 않으면 정렬 범위에서 적절한 곳(첫 요.. [알고리즘] 버블 정렬(Bubble Sort) - 코딩밥상 버블 정렬이란? 버블 정렬이란 이름은 물 속 깊은 곳에서 수면을 향호 올라오는 거품들의 모습처럼 데이터를 정렬하기에 붙여진 이름입니다. 즉 자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬을 수행합니다. 이웃한 요소끼리 데이터를 교환하므로 교환 전에 먼저 이웃끼리 비교하여 바른 순서로 위치해 있는지 확인해야 합니다. 예를들어 5 1 6 4 2 3 을 오름차순으로 버블정렬 하면, 5 1 6 4 2 3 -> 1 5 6 4 2 3 -> 1 5 4 6 2 3 -> 1 5 4 2 6 3 -> 1 5 4 2 3 6 1 5 4 2 3 6 -> 1 4 5 2 3 6 -> 1 4 2 5 3 6 -> 1 4 2 3 5 6 1 4 2 3 5 6 -> 1 2 4 3 5 6 -> 1 2 3 4 5 6 1 2 3 4.. 이전 1 다음