셸 정렬 도날드 셸(D. L. Shell)에 의해 고안되었으며, 퀵 정렬이 나오기 전까지 가장 빠른 정렬 알고리즘이었다. 셸 정렬은 단순 삽입 정렬의 장점은 살리면서 단점은 보완하여 좀 더 빠르게 정렬 가능한 정렬 알고리즘이다. 일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟루를 줄이는 정렬 알고리즘이다. 단순 삽입 정렬 장점 : 배열이 이미 많은 부분 정렬되어 있을 시 정렬 속도가 굉장히 빠르다. 단순 삽입 정렬 단점 : 삽입할 곳이 멀리 떨어져 있을 시 거리에 비례해서 이동하는 횟수가 많아진다. -> 삽입할 위치와 현재 위치 사이에 위치한 요소들을 현재 위치까지 모두 한 칸씩 이동 시키고 삽입해야한다...
단순 삽입 정렬(straight insertion sort) 단순 삽입 정렬은 0 ~ n-1까지 n개의 배열이 있다고 가정했을 때, 1번 위치 요소부터 선택을 시작하여 현재 정렬되지 않은 부분의 첫 번째 요소를 선택하여 선택한 위치 앞 부분 요소들과 비교를 하여 정렬기준에 따라 해당 되는 위치에 삽입을 수행해나가는 정렬 알고리즘이다. 단순 삽입정렬은 셔틀 정렬(shuttle sort)라고도 부른다. // 선택 정렬 부분 static void insertionSort(int[] a, int n){ for(int i = 1; i 0 && a[j-1] > tmp ;..
단순 선택 정렬(straight selection sort) 단순 선택 정렬은 두 가지 부분으로 볼 수 있다. 하나는 현재까지 정렬된 부분과 나머지 정렬해야하는 부분이다. 무슨 말인가? 즉, 단순 선택 정렬은 배열의 가장 앞 쪽부터 시작해서 정렬하고자하는 기준에 따라 정렬되지 않은 부분을 모두 검색하며, 그 중 현재 정렬되어야 할 위치에 기준에 따른 값을 정렬시키는 방식이다. 버블 정렬과 비교했을 경우 버블 정렬은 이웃하는 요소들을 검색하며, 정렬기준에 따라 이웃 간 교환이 발생한다면, 단순 선택 정렬은 정렬되지 않은 부분들을 모두 검색하여 그 중 정렬기준에 맞는 값을 현재 정렬해야하는 위치와 교환하는 방식이다. static int change = 0; //교환횟수 static int search = 0..
버블 정렬(bubble sort) 이웃한 두 요소의 대소관계를 비교하여 교환하는 알고리즘. 단순교환정렬이라고도 부른다. 액체안의 공기 방울이 위로 보글보글 올라오는 모습에서 착안했다고 한다. 버블 알고리즘에 관하여 3가지 방법으로 구현한 코드와 성능에 대해서 확인해보며, 정렬이 어떻게 진행되는가는 진행되는 과정을 출력으로 확인해보고, 3가지 방법에서 수행되는 교환횟수, 비교횟수를 확인해보자. 동일한 조건 설정을 위하여 {1,3,9,4,7,8,6}의 요소값을 갖는 크기가 7인 배열을 사용한다. 아래 출력되는 결과를 통해서도 확인해 볼 수 있듯이 버블정렬은 두 요소값을 비교할 시 값이 같으면 교환이 이루어지지 않는다. 즉, 정렬 전후로 두 요소의 값에 따라 전체적인 위치는 변경되더라도 두 요소 사이에 순서는..
정렬 알고리즘이란 ? 정렬 : 이름, 학번 , 키 등 핵심 항목의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다. 오름차순(ascending order) 정렬 : 정렬하고자 하는 기준에 따라 가장 작은 값부터 시작하여 정렬하는 방식 내림차순(descending order) 정렬 : 오름차순과 반대로 가장 큰 값부터 시작하여 작은 값으로 정렬하는 방식 정렬 알고리즘의 안정성 정렬 알고리즘의 경우 안정된 알고리즘과 안정되지 않은 알고리즘으로 나눌 수 있다. 안정된 알고리즘 : 정렬 기준에 따라 정렬 시 동일한 값을 갖는 요소에 대해서 정렬 전후 순서가 유지되는 알고리즘 안정되지 않은 알고리즘 : 동일한 값에 대해서 정렬 전후 반드시 순서가 보장되지 않는 알고리즘 내부 정렬과 외부 정렬 ..
8-Queen problem 8-Queen problem이란 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장한다. 19세기 유명한 수학자 카를 프리드리히 가우스가 잘못 된 해답을 내놓은 것으로도 잘 알려져있다고 한다. 해당 문제는 8 X 8 체스판에 8개의 퀸을 서로가 공격할 수 없도록 배치하는 문제로 92가지가 있다고 한다. 추가적으로 체스에서 퀸은 가로,세로,대각선 방향으로 공격이 가능하다. 분기 조작 분기란 가지가 뻗어 나가듯이 문제를 나누어 푸는 과정을 의미합니다. 총 가지수로 봤을 경우 각 퀸은 미리 놓인 자리를 제외한 모든 자리에 놓일 수 있기에 64 * 63 * 62 ... = 178 =178,462,987,637,760의 경우가 있습니다. 이와같은 경우를 구하기 위해서 각 행 또..