정렬은 객체에 대해 수행하는 기본 작업 중 하나입니다. 어린 시절에도 아이들은 사고력이 발달함에 따라 분류하는 법을 배웁니다. 컴퓨터와 소프트웨어도 예외는 아닙니다. Java에는 매우 다양한 정렬 알고리즘이 있습니다 . 나는 그들이 무엇이며 어떻게 작동하는지 확인하는 것이 좋습니다. 언젠가 면접에서 그들 중 한 명에 대해 묻는다면?
소개
정렬 요소는 개발자가 반드시 알아야 하는 알고리즘 범주 중 하나입니다. 내가 학교에 다닐 때 컴퓨터 과학이 한때 진지하게 받아들여지지 않았다면 오늘날의 학생들은 정렬 알고리즘을 구현하고 이해할 수 있어야 합니다. 가장 단순한 기본 알고리즘은 for 루프를 사용하여 구현됩니다. 당연히 배열과 같은 요소 모음을 정렬하려면 어떻게든 모음을 살펴봐야 합니다. 예를 들어:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
이 코드 세그먼트에 대해 무엇을 말할 수 있습니까? int i인덱스( )를 0에서 배열의 마지막 요소로 변경하는 루프가 있습니다 . 사실, 우리는 단순히 배열의 각 요소를 가져와 그 내용을 인쇄하고 있습니다. 배열의 요소가 많을수록 코드를 완료하는 데 더 오래 걸립니다. 즉, n요소의 수인 if는 n = 10when보다 프로그램 실행 시간이 두 배 더 오래 걸립니다 n = 5. 프로그램에 단일 루프가 있는 경우 실행 시간은 선형적으로 증가합니다. 요소가 많을수록 실행 시간이 길어집니다. 위의 알고리즘은 선형 시간(n의 선형 함수)에서 작동하는 것으로 밝혀졌습니다. 이러한 경우 알고리즘의 복잡도는 "O(n)"이라고 합니다. 이 표기법은 "big O" 또는 "점근적 동작"이라고도 합니다. 그러나 당신은 "
가장 간단한 정렬 알고리즘(버블 정렬)
배열이 있고 그것을 통해 반복할 수 있다고 가정합니다. 엄청난. 이제 오름차순으로 정렬해 보겠습니다. 이것은 무엇을 의미 하는가? 이는 두 개의 요소(예: a = 6, b = 5)가 주어졌을 때 재정렬해야 하며 aif b가 (if ) a보다 크다는 것을 의미합니다. 인덱스를 사용하여 컬렉션 작업을 수행할 때(배열의 경우처럼) 이것은 무엇을 의미합니까? 인덱스가 a인 요소가 인덱스가 있는 요소 ( )보다 크면 요소를 교환해야 함을 의미합니다. 장소를 바꾸는 방법은 다양합니다. 그러나 우리는 간단하고 이해하기 쉽고 기억하기 쉬운 기술을 사용할 것입니다. ba > bbarray[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
이제 다음과 같이 작성할 수 있습니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
보시다시피 요소가 실제로 교체되었습니다. 배열에 요소가 하나만 있는 경우 array[i] < array[i-1]인덱스 에 대해 식이 유효하지 않기 때문에 인덱스 1부터 시작했습니다 0. 이렇게 하면 배열에 요소가 없거나 하나의 요소만 있는 경우로부터 우리를 보호할 수 있으며 코드가 더 보기 좋아집니다. 그러나 한 번의 패스로는 정렬을 수행하기에 충분하지 않기 때문에 결과 배열은 여전히 정렬되지 않습니다. 정렬된 배열을 얻을 때까지 패스를 반복해서 수행하는 또 다른 루프를 추가해야 합니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
그래서 우리는 첫 번째 정렬 알고리즘을 마쳤습니다. while더 이상 반복이 필요하지 않다고 결정할 때까지 외부 루프( )를 반복합니다 . 기본적으로 각각의 새 반복 전에 배열이 정렬되어 있고 더 이상 반복할 필요가 없다고 가정합니다. 따라서 요소를 통해 순차적으로 이동하고 이 가정을 확인합니다. 그러나 요소의 순서가 맞지 않으면 요소를 교환하고 이제 요소의 순서가 올바른지 보장할 수 없음을 이해합니다. 이는 또 다른 반복을 수행해야 함을 의미합니다. 예를 들어 [3, 5, 2]. 5이상입니다 3— 모든 것이 좋습니다. 그러나 2는 5. 그러나 [3, 2, 5]다른 패스가 필요합니다.3 > 2교체해야 합니다. 루프 내에서 루프를 사용하기 때문에 알고리즘의 복잡성이 증가합니다. n요소 가 주어 지면 n * n, 즉 가 됩니다 O(n^2). 이를 2차 복잡도라고 합니다. 일반적으로 얼마나 많은 반복이 필요할지 정확히 알 수 없습니다. 알고리즘의 복잡도 표현은 최악의 경우 복잡도가 어떻게 증가하는지를 보여줍니다. 즉, 요소의 수가 n변경됨에 따라 실행 시간이 얼마나 증가할지를 나타냅니다. 버블 정렬은 가장 단순하고 가장 비효율적인 정렬 알고리즘 중 하나입니다. 때로는 "멍청한 정렬"이라고도 합니다. 이 주제에 대한 자료:
또 다른 정렬 알고리즘은 선택 정렬입니다. 또한 2차 복잡도가 있지만 나중에 자세히 설명합니다. 그래서 아이디어는 간단합니다. 각 패스에서 가장 작은 요소를 선택하고 처음으로 이동합니다. 또한 각 패스는 오른쪽으로 한 단계 시작합니다. 즉, 첫 번째 패스는 0번째 요소에서 시작하고 두 번째 패스는 첫 번째 요소에서 시작하는 식입니다. 다음과 같이 표시됩니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
이 정렬은 동일한 요소(요소를 정렬하는 데 사용하는 특성과 관련하여)가 상대 위치를 변경할 수 있기 때문에 불안정합니다. 선택 정렬 에 대한 Wikipedia 기사에 좋은 예가 있습니다 . 이 주제에 대한 자료:
삽입 정렬도 루프 내에 루프가 있기 때문에 2차 복잡성이 있습니다. 삽입 정렬이 다른 점은 무엇입니까? 이 정렬 알고리즘은 "안정적"입니다. 이는 동일한 요소가 상대적인 순서를 변경하지 않음을 의미합니다. 다시 말하지만, 우리는 우리가 정렬하는 특성의 관점에서 동일함을 의미합니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
셔틀 정렬
또 다른 간단한 정렬 알고리즘인 셔틀 정렬이 있습니다. 양방향 버블 정렬 또는 칵테일 셰이커 정렬이라고도 합니다. 이러한 대체 이름은 셔틀 정렬이 우주 왕복선에 관한 것이 아님을 알려줍니다. 그것은 앞뒤로 움직이는 것에 관한 것입니다. 이제 이 알고리즘을 생각할 때 그것을 생각할 수 있습니다. 알고리즘의 본질은 무엇입니까? 알고리즘의 핵심은 왼쪽에서 오른쪽으로 반복하면서 요소를 교체하고 다른 방향에 남아 있는 요소를 교체해야 하는지 확인하는 것입니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
또 다른 간단한 정렬 알고리즘은 쉘 정렬입니다. 요지는 버블 정렬과 비슷하지만 각 반복에서 비교되는 요소 사이에 다른 간격이 있습니다. 반복할 때마다 반으로 잘립니다. 구현은 다음과 같습니다.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
이러한 간단한 정렬 알고리즘 외에도 더 복잡한 정렬 알고리즘도 있습니다. 예를 들어, 병합 정렬. 두 가지 유의할 사항이 있습니다. 첫째, 재귀가 여기서 우리를 구해줍니다. 둘째, 알고리즘의 복잡도는 우리가 익숙한 것처럼 더 이상 2차식이 아닙니다. 이 알고리즘의 복잡도는 대수적입니다. 이것은 O(n log n). 그럼 구현해 봅시다. 먼저 정렬 메서드에 대한 재귀 호출을 작성합니다.
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
이제 구현에 기본 작업을 추가해 보겠습니다. 슈퍼 메서드는 다음과 같습니다.
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
다음을 호출하여 예제를 실행할 수 있습니다.mergeSort(array, 0, array.length-1). 보시다시피 프로세스는 정렬해야 하는 섹션의 시작 및 끝 표시와 함께 입력 배열을 수락하는 것으로 귀결됩니다. 정렬이 시작되면 이들은 배열의 시작과 끝입니다. 그런 다음 배열을 분할할 인덱스인 구분 기호를 계산합니다. 배열을 두 부분으로 나눌 수 있으면 배열의 두 부분에 대해 재귀적으로 정렬 메서드를 호출합니다. 정렬된 섹션을 삽입할 보조 버퍼를 준비합니다. 그런 다음 정렬할 섹션의 시작 부분에 인덱스를 설정하고 빈 버퍼의 각 요소를 탐색하여 가장 작은 요소로 채웁니다. 인덱스가 가리키는 요소가 구분 기호가 가리키는 요소보다 작으면 해당 요소를 버퍼에 넣고 인덱스를 이동합니다. 그렇지 않으면, 구분 기호가 가리키는 요소를 버퍼에 넣고 구분 기호를 이동합니다. 구분 기호가 정렬 중인 섹션의 경계를 벗어나거나 전체 배열을 채우는 즉시 지정된 범위가 정렬된 것으로 간주됩니다.이 주제에 대한 자료:
또 다른 흥미로운 정렬 알고리즘은 카운팅 정렬입니다. 여기서 알고리즘 복잡도는 입니다 O(n+k). 여기서 n는 요소의 수이고 는 k요소의 최대값입니다. 이 알고리즘에는 한 가지 단점이 있습니다. 배열의 최소값과 최대값을 알아야 합니다. 다음은 계수 정렬의 예입니다.
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
미리 최소값과 최대값을 알아야 하는 경우 매우 불편함을 알 수 있습니다. 여기에 또 다른 알고리즘이 있습니다. 기수 정렬입니다. 여기서는 알고리즘을 시각적으로만 제시하겠습니다. 구현을 위한 추가 자료를 참조하십시오. 자료:
이제 디저트를 먹을 시간입니다. 가장 유명한 정렬 알고리즘 중 하나인 빠른 정렬입니다. 로그 복잡도가 있습니다: O(n log n). 이 정렬 알고리즘은 Tony Hoare가 개발했습니다. 흥미롭게도 그는 소련에 살면서 모스크바 대학에서 기계 번역을 공부하고 러시아어-영어 관용구집을 개발하면서 그것을 발명했습니다. 게다가 Java는 NET에서 이 알고리즘의 더 복잡한 버전을 사용합니다 Arrays.sort. 어떻습니까 Collections.sort? "내부적으로" 항목이 어떻게 정렬되는지 살펴보지 않으시겠습니까? 코드는 다음과 같습니다.
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
이것은 모두 매우 무서운 것이므로 파헤쳐 봅시다. 입력 배열( 소스)에 대해 왼쪽( ) 및 오른쪽( ) int[]이라는 두 개의 마커를 만듭니다 . 첫 번째 메서드 호출 중에 배열의 시작과 끝에 해당합니다. 그런 다음 적절하게 이름이 지정된 피벗 요소를 식별합니다 . 그 후, 우리의 임무는 보다 작은 값을 왼쪽으로 이동 하고 큰 값은 오른쪽으로 이동하는 것입니다. 이를 위해 먼저 보다 큰 값을 찾을 때까지 마커를 이동합니다 . 더 작은 값이 발견되지 않으면LRpivotpivotpivotLpivot
L은
pivot.
R그런 다음 보다 작은 값을 찾을 때까지 마커를 이동합니다
pivot. 더 큰 값이 없으면 와
R같습니다
pivot.
L다음으로 마커가 마커 앞에 있거나 마커와 일치하는 경우 요소가 요소보다 작은
R경우 요소를 교환하려고 합니다 . 그런 다음 오른쪽으로 1만큼 이동 하고 왼쪽으로 1만큼 이동합니다. 마커가 마커 너머로 이동 하면 스와핑이 완료되었음을 의미합니다. 작은 값은 의 왼쪽에 있고 큰 값은 오른쪽에 있습니다.
LRLRLRpivotpivot. 그런 다음 하위 배열에서 동일한 정렬 방법을 재귀적으로 호출합니다. 정렬할 섹션의 시작 부분부터 오른쪽 마커까지, 왼쪽 마커부터 정렬할 섹션의 끝까지 호출합니다. 처음부터 오른쪽 마커까지 왜? 반복이 끝나면 오른쪽 마커가 왼쪽 부분의 경계가 될 만큼 충분히 움직인다는 것이 밝혀졌기 때문입니다. 이 알고리즘은 단순 정렬보다 복잡하므로 스케치하는 것이 가장 좋습니다. 흰 종이에 다음과 같이 적습니다. 4 2 6 7 3. 그런 다음
pivot가운데, 즉 6번 아래에 적습니다. 동그라미를 치십시오. 4 미만은 ,
L3 미만은 을 씁니다
R. 6보다 작은 4, 6보다 작은 2. 지나갈 수 없기 때문에 결국 위치
L로 이동합니다.
pivotLpivot, 조건에 따라. 4 2 6 7 3을 다시 쓰세요. 6 (
pivot)에 동그라미를 치고
L그 아래에 넣으세요. 이제
R마커를 이동합니다. 3은 6보다 작으므로
R마커를 3에 놓습니다. 3은 6( )보다
pivot작으므로
swap. 결과를 쓰십시오: 4 2 3 7 6. 여전히 6이기 때문에 6에 동그라미를 치십시오
pivot. 마커
L는 3에 있습니다. 마커는 6에 있습니다. 을 넘어 움직일
R때까지 마커를 이동한다는 것을 기억하십시오 . 다음 번호로 이동합니다 . 여기서는 두 가지 가능성을 살펴보고자 합니다. 1) 두 번째 숫자가 7인 경우와 2) 7이 아닌 1인 경우입니다.
두 번째 숫자가 1인 경우: 마커를 1로 이동합니다 . 하는 한
LRLLLL마커는 보다 작은 숫자를 가리킵니다
pivot. 그러나 마커가 .보다 큰 숫자를 가리키는
R경우에만 R을 이동할 수 있기 때문에 6에서 벗어날 수 없습니다 . 1은 6보다 작기 때문에 a를 수행하지 않습니다 . 현재 상황을 쓰십시오: 4 2 3 1 6. 6에 동그라미를 치십시오( ). 이동 하고 이동을 멈춥니다. 움직이지 않는다. 우리는 스왑을 수행하지 않습니다. 한 위치 씩 이동합니다 . 마커를 1 아래에 씁니다. 마커가 범위를 벗어났습니다. 범위를 벗어났기 때문에 아무것도 하지 않습니다. 그러나 우리는 4 2 3 1을 다시 씁니다. 왜냐하면 이것은 (6) 보다 작은 좌변이기 때문입니다 . 새로운 것을 선택 하고 모든 것을 다시 시작하십시오 :)
두 번째 숫자가 7인 경우:RpivotswappivotLpivotRLRRLLpivotpivot
마커를 7로 이동합니다
L. 오른쪽 마커는 이미 피벗을 가리키고 있기 때문에 이동할 수 없습니다. 7이 보다 크므
pivot로
swap. 결과를 쓰십시오: 4 2 3 6 7. 6에 동그라미를 치십시오
pivot. 마커
L는 이제 7로 이동하고 마커는 3으로 이동합니다 . 요소가 1개뿐이므로 부품을 처음부터 끝까지
R정렬하는 것은 의미가 없습니다 .
L그러나 정렬을 위해 4의 부분을 마커로 보냅니다
R. 우리는 a를 선택
pivot하고 다시 시작합니다 :) 언뜻보기에 다음과 같은 많은 값을 추가하면
pivot, 그러면 알고리즘을 깨뜨릴 것입니다. 그러나 이것은 사실이 아닙니다. 까다로운 조합을 생각하고 종이에 모든 것이 정확하다고 확신하고 그러한 간단한 작업이 신뢰할 수있는 정렬 메커니즘을 구현한다는 사실에 감탄할 수 있습니다. 유일한 단점은 이 정렬 알고리즘이 안정적이지 않다는 것입니다.
pivot다른 요소가 before 부분으로 교체되기 전에 요소 중 하나가 이전에 발견되면 교체로 인해 동일한 요소의 상대적 순서가 변경될 수 있기 때문입니다
pivot.
GO TO FULL VERSION