태니의 기록

계속 해서 퀵정렬을 살펴보자. 우선 앞에서 배운 내용을 바탕으로 퀵정렬을 구현해보면 아래와 같다. [퀵정렬 구현] - JAVA import java.util.*; public class QuickSort{ private static void quickSort(int[] arr) { //quickSort 함수 선언 quickSort(arr,0,arr.length-1); //정렬을 할 배열을 받아서 시작 위치와 끝나는 위치를 정하기 } //start, end, 파티션을 나눌 범위를 설정해 인자로 받음 private static void quickSort(int[] arr, int start, int end) { //재귀함수를 본격적으로 호출 int part2 = partition(arr,start,end);..

일반적으로 가장 많이 사용 되는 퀵정렬(Quick Sort)에 대해 공부해 보자. 퀵정렬은 이름처럼 졍렬 속도가 매우 빠른 것에서 착안하여 알고리즘 개발자 찰스 앤터니 리터드 호어(C. A. R. Hoare)가 착안해 직접이름을 붙였다. [개요] [배열을 두그룹으로 나누기] 그룹을 나누기 위해서는 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이하의 요소들을 오른 쪽으로 옮겨야 한다. - a[pl] >= x 가 성렵하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔함 - a[pl] pr +1 이면 다음과 같은 그룹이 생기게 된다. - 피벗과 같은 값을 갖는 그룹 : a[pr +1], ··· , a[pl-1] 만일 피벗과 같은 값을 갖는 그룹이 만들어 진다면, 이때도 전과 마찬가지로 동일한 요소를 교환하면 된다(어..

오늘은 정렬에 대해서 공부하고자 한다. 정렬이란 데이터의 집합을 일정한 순서로 나열하는 집합을 의미한다. 즉 알고리즘을 이용해 데이터를 정렬하게 되면 검색을 쉽게 할 수 있다. 정렬 알고리즘의 핵심 요소는 교환, 삽입, 선택이다. 대부분의 정렬 알고리즘은 이 3가지 요소들을 응용한 것이다. 대표적인 정렬 알고리즘은 크게 8종류가 있는데 아래와 같다. 1. 버블 정렬 : 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라서 교환을 하는 알고리즘으로 단순교환정렬이라고도 한다. 2. 단순선택정렬 : 가장 작은 요소를 맨앞으로 이동하고, 두번째 작은 요소는 맨앞에서 두번째로 이동하는 등의 작업을 반복하는 것이다. 3. 단순삽입정렬 : 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 "삽입하는" 작업을 방법하여 정..