shell sort c with examples
C ++의 쉘 정렬 기법 : 전체 개요.
쉘 정렬은 종종 삽입 정렬보다 개선 된 것으로 불립니다. 삽입 정렬에서는 요소를 비교하고 적절한 위치에 배치하기 위해 1 씩 증가합니다.
셸 정렬에서 목록은 여러 개의 작은 하위 목록으로 분류되어 정렬됩니다. 목록에 연속적인 요소가있을 필요는 없습니다. 대신 쉘 정렬 기술은 '간격'이라고도하는 증분 i를 사용하고이를 사용하여 'i'요소가 떨어져있는 요소 목록을 만듭니다.
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
Android 용 최고의 VR 앱은 무엇인가요
학습 내용 :
일반 알고리즘
쉘 정렬을위한 일반적인 알고리즘은 다음과 같습니다.
shell_sort (A, N)
여기서 A – 정렬 할 목록; N – gap_size
gap_size = N, 플래그 = 1 설정
gap_size> 1 또는 flag = 1 인 동안 반복
시작하다
플래그 설정 = 0
set gap_size = (gap_size + 1) / 2
종료
for i = 0 to i<(N-gap_size) repeat
시작하다
A (i + gap_size)> A (i) 인 경우
스왑 A (i + gap_size), A (i)
플래그 설정 = 0
종료
종료
따라서 위의 알고리즘에서 먼저 쉘 정렬을 사용하여 배열 A를 정렬하기위한 간격 인 N을 설정합니다. 다음 단계에서는 간격을 사용하여 배열을 하위 배열로 나눕니다. 그런 다음 다음 단계에서 루프의 끝에서 정렬 된 배열을 얻을 수 있도록 각 하위 배열을 정렬합니다.
다음으로 그림 표현을 사용하여 쉘 정렬을 더 잘 이해하기위한 자세한 예를 고려해 보겠습니다.
삽화
예제를 통해 Shell 정렬을 설명해 보겠습니다.
다음 10 개 요소 배열을 고려하십시오.
3의 간격을 제공하면 3 개의 요소가 떨어져있는 각 요소가있는 다음 하위 목록이 있습니다. 그런 다음이 세 가지 하위 목록을 정렬합니다.
정렬 된 하위 목록과 세 개의 정렬 된 하위 목록을 결합한 후 얻은 결과 목록은 다음과 같습니다.
정렬 된 하위 배열을 병합 한 후 얻은 위 배열은 거의 정렬되어 있습니다. 이제이 목록에서 삽입 정렬을 수행하고 전체 배열을 정렬 할 수 있습니다. 이 마지막 단계는 참조 용으로 아래에 나와 있습니다.
위에서 볼 수 있듯이 셸 정렬을 수행하고 정렬 된 하위 목록을 병합 한 후 목록을 완전히 정렬하려면 세 번만 이동하면됩니다. 따라서 배열을 정렬하는 데 필요한 단계 수를 크게 줄일 수 있음을 알 수 있습니다.
하위 목록을 만들기위한 증분 선택은 쉘 정렬의 고유 한 기능입니다.
C ++ 예
아래의 C ++에서 쉘 정렬 구현을 살펴 보겠습니다.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i 산출:
정렬 할 배열 :
45 23 53 43 18 24 8 95101
쉘 정렬 후 배열 :
8 18 23 24 43 45 53 95101
그림에서 사용한 것과 동일한 목록을 사용했으며 처음에 두 개의 하위 목록을 만든 다음 간격을 더 좁히는 것으로 시작하는 것을 볼 수 있습니다. 지정된 간격에 따라 하위 목록이 생성되면 각 하위 목록을 정렬합니다. 모든 하위 목록이 정렬되면 거의 정렬 된 목록을 얻습니다. 이제이 목록은 거의 이동하지 않는 기본 삽입 정렬을 사용하여 정렬 할 수 있습니다.
다음으로 Java 언어를 사용하여 쉘 정렬을 구현해 보겠습니다.
자바 예
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i 산출:
정렬 할 배열 :
45 23 53 43 18 24 8 95101
쉘 정렬 후 배열 :
8 18 23 24 43 45 53 95101
우리는 C ++ 및 Java 프로그램 모두에서 쉘 정렬에 대해 동일한 로직을 구현했습니다. 따라서 Java 프로그램에서 위에서 설명한 것처럼 먼저 배열을 하위 배열로 나눈 다음 정렬하여 완전한 정렬 배열을 얻습니다.
결론
쉘 정렬은 삽입 정렬보다 개선 된 매우 효율적인 알고리즘입니다.
삽입 정렬은 요소를 1 씩 증가시키는 방식으로 작동하는 반면, 쉘 정렬은 매개 변수 'gap'을 사용하여 배열을 요소가 '간격'떨어져있는 하위 배열로 나눕니다. 그런 다음 삽입 정렬을 사용하여 개별 목록을 정렬하여 전체 정렬 된 배열을 얻을 수 있습니다.
셸 정렬은 삽입 정렬보다 더 빠르게 수행되며 삽입 정렬과 비교할 때 배열을 정렬하는 데 더 적은 이동이 필요합니다. 다가오는 자습서에서는 데이터 구조를 정렬하기위한 힙 정렬 기술에 대해 모두 살펴볼 것입니다.
=> 처음부터 C ++를 배우려면 여기를 방문하십시오.
추천 도서