퀵정렬(Quick Sort)이란? 퀵정렬은 분할정복에 기반한 알고리즘이다. 분할정복이란 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 개념이다. 퀵 정렬은 아래와 같은 과정으로 분할 정복을 이용해 정렬을 한다. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다. 1에서 나눈 데이터 집합들을 다시 1처럼 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다. 1,2 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻는다. 이를 토대로 예시를 들어보겠다. 요소 5를 기준으로, 5보다 작은 요소는 왼쪽, 5보다 큰 요소는 오..
삽입 정렬(Insertion Sort) 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 삽입 정렬도 버블 정렬만큼 구현이 간단해서 프로그래머들에게 애용된다. 삽입 정렬은 아래와 같은 과정을 진행한다.(오름차순 정렬) 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1' 이다. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다. 그렇지 않다면 이 요소를 정렬 대상에서 뽑아내고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다...
정렬은 사전적 의미로 "물건 등을 가지런히 늘어 세우다" 라는 뜻을 갖고 있다. 우리는 정렬을 왜 할까? 이유는 간단하다. 찾을려고 하는 것을 쉽게 찾고싶어서이다. 즉, 탐색을 위해 정렬을 한다는 것이다. 앞으로 정렬 알고리즘 중 활용도가 높은 버블 정렬, 삽입 정렬, 퀵 정렬 3 가지에 대해 알아볼 예정이고 먼저 버블 정렬(Bubble Sort)부터 소개하겠다. 버블 정렬(Bubble Sort) 버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다. 버블 정렬은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다. 이해를 돕기위해 제멋대로 나열되어 있는 수의 집합을 오름차순으로 정렬해보..
