C 언어 빠 른 정렬 인 스 턴 스 코드

빠 른 정렬 은 거품 법 정렬 에 대한 개선 이다.
빠 른 정렬 알고리즘 의 기본 사상 은 정렬 할 수 있 는 수 를 좌우 두 부분 으로 나 누고 그 중의 일부분 의 모든 데 이 터 는 다른 부분의 데이터 보다 작다.그리고 나 누 어 얻 은 두 부분의 데 이 터 를 똑 같이 구분 하고 이상 의 구분 작업 을 반복 하여 정렬 할 데이터 가 질서 가 있 을 때 까지 반복 하 는 것 이다.
기본 사상 에 따라 빠 른 정렬 에 대한 인식 이 깊 지 않 을 수 있 습 니 다.그 다음 에 n 개의 무질서 수열 A[0],A[1],A[n-1]에 대해 빠 른 정렬 방법 으로 오름차 순 배열 을 예 로 들 어 설명 합 니 다.
(1)두 변수 low 와 high 를 정의 하고 low,high 를 정렬 할 시퀀스 의 시작 요소 와 마지막 요소 의 아래 표 시 를 설정 합 니 다.첫 번 째,low 와 high 의 수 치 는 각각 0 과 n-1 이 고 그 다음 의 매번 수 치 는 분 단 된 시퀀스 의 시작 요소 와 마지막 요소 의 아래 표 시 를 통 해 결정 된다.
(2)변 수 키 를 정의 합 니 다.그 다음 에 키 의 값 을 기준 으로 배열 A 를 좌우 두 부분 으로 나 눕 니 다.보통 키 값 은 정렬 서열 을 진행 할 첫 번 째 요소 값 입 니 다.첫 번 째 수 치 는 A[0]이 고 나중에 안정 적 인 개 그 세척 끝 에 따라 서열 을 나 누 는 시작 요소 에 따라 결정 된다.
(3)하 이 가 가리 키 는 배열 요 소 를 왼쪽으로 스 캔 하고 스 캔 하 는 동시에 하 이 로 표 시 된 배열 요 소 를 차례대로 기준 치 key 와 비교 하여 하 이 가 low 보다 크 지 않 거나 기준 치 key 보다 작은 배열 요 소 를 찾 은 다음 에 이 값 을 low 가 가리 키 는 배열 요소 에 할당 하고 low 를 오른쪽으로 한 위 치 를 옮 깁 니 다.
(4)low 가 여전히 high 보다 작 으 면 low 가 가리 키 는 배열 요소 에서 오른쪽으로 스 캔 을 시작 합 니 다.스 캔 하 는 동시에 아래 에 low 로 표 시 된 배열 요소 값 을 순서대로 구분 하 는 기준 치 key 와 비교 작업 을 합 니 다.low 가 high 보다 작 지 않 거나 기준 치 key 보다 큰 첫 번 째 배열 요 소 를 찾 은 다음 에 이 값 을 high 가 가리 키 는 배열 요소 에 부여 하고 high 를 왼쪽 으로 이동 합 니 다.
(5)반복 절차(3)(4),low 의 식 이 high 보다 작 지 않 을 때 까지 이 때 성공 적 으로 구분 한 좌우 두 부분 은 각각 A[low...pos-1]과 A[pos+1...high]이다.그 중에서 pos 아래 에 표 시 된 배열 요소 의 값 은 구분 하 는 기준 치 key 이기 때문에 구분 이 끝 날 때 다음 에 pos 로 표 시 된 배열 요 소 를 key 로 할당 해 야 한다.
(6)구 분 된 좌우 두 부분 A[low...pos-1]과 A[pos+1...high]는 질서 있 는 서열 을 얻 을 때 까지 상기 조작 절 차 를 계속 사용 하여 구분 합 니 다.
독자 의 이 해 를 깊이 있 게 하기 위해 다음 코드 를 통 해 빠 른 정렬 의 구체 적 인 실현 방법 을 알 아 보 겠 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#define N 6
int partition(int arr[], int low, int high){
  int key;
  key = arr[low];
  while(low<high){
    while(low <high && arr[high]>= key )
      high--;
    if(low<high)
      arr[low++] = arr[high];
    while( low<high && arr[low]<=key )
      low++;
    if(low<high)
      arr[high--] = arr[low];
  }
  arr[low] = key;
  return low;
}
void quick_sort(int arr[], int start, int end){
  int pos;
  if (start<end){
    pos = partition(arr, start, end);
    quick_sort(arr,start,pos-1);
    quick_sort(arr,pos+1,end);
  }
  return;
}
int main(void){
  int i;
  int arr[N]={32,12,7, 78, 23,45};
  printf("    
");
  for(i=0;i<N;i++)
    printf("%d\t",arr[i]);
  quick_sort(arr,0,N-1);
  printf("
     
");
  for(i=0; i<N; i++)
    printf("%d\t", arr[i]);
  printf ("
");
  system("pause");
  return 0;
}

실행 결과:
정렬 전
32    12    7    78    23    45
정렬 후
7    12    23    32    45    78
위의 코드 에서 앞에서 소개 한 절차 에 따라 빠 른 정렬 알고리즘 을 실현 했다.다음은 설명도 로 첫 번 째 구분 작업 을 보 여 준다.
첫 번 째 구분 작업 에서 먼저 초기 설정 을 합 니 다.key 의 값 은 구분 하 는 기준 입 니 다.그 값 은 배열 의 첫 번 째 요소 값 이 고 위의 정렬 서열 에서 첫 번 째 요소 값 32 입 니 다.이 동시에 low 를 배열 할 배열 의 첫 번 째 요소 의 아래 표 로 설정 합 니 다.첫 번 째 정렬 작업 을 할 때 그 값 은 0 입 니 다.하 이 를 정렬 할 서열 의 마지막 요소 로 설정 하고 위의 정렬 서열 에서 첫 번 째 값 은 5 입 니 다.먼저 하 이 라 고 표 시 된 배열 요 소 를 key 와 비교 합 니 다.이 요소 의 값 이 key 보다 크기 때문에 하 이 는 왼쪽으로 한 위 치 를 이동 하여 계속 스 캔 합 니 다.다음 값 은 23 이 고 key 의 값 보다 작 기 때문에 23 대 값 을 low 가 가리 키 는 배열 요소 로 표시 합 니 다.그 다음 에 low 를 오른쪽으로 한 위 치 를 옮 기 고 low 가 가리 키 는 배열 요소 의 값 을 key 와 비교 합 니 다.다음 12,7 은 모두 key 보다 작 기 때문에 low 는 오른쪽 으로 스 캔 을 계속 합 니 다.아래 표 시 된 low 가 가리 키 는 배열 요소 의 값 이 78 즉 key 보다 클 때 까지 78 대 치 를 하 이 가 가리 키 는 배열 요소 에 부여 하고 하 이 를 왼쪽으로 한 위 치 를 옮 깁 니 다.다음은 low 가 더 이상 high 보다 작 지 않 기 때문에 구분 이 끝 납 니 다.주의해 야 할 것 은 구분 하 는 과정 에서 스 캔 한 값 과 key 의 값 을 비교 하 는 것 입 니 다.key 보다 작 으 면 이 값 을 배열 의 다른 요소 에 할당 합 니 다.이 요소 의 값 은 변 하지 않 았 습 니 다.그림 에서 이 점 을 알 수 있 기 때문에 구분 의 마지막 에 구분 기준 으로 하 는 key 값 을 pos 로 표 시 된 배열 요소 에 부여 해 야 합 니 다.이 요 소 는 다음 구분 작업 에 참여 하지 않 습 니 다.

                                                                      일차 구분 조작
1 차 구분 이 끝 난 후에 좌우 두 부분의 서열 A[0],A[1],A[2]와 A[4],A[5]를 얻 었 고 계속 구분 했다.즉,올림픽 을 나 눈 후에 얻 은 두 부분의 서열 을 질서 있 는 서열 을 얻 을 때 까지 계속 구분 하 는 것 이다.
이상 은 C 언어의 빠 른 정렬 에 대한 상세 한 설명 입 니 다.학습 에 도움 이 되 기 를 바 랍 니 다. C 언어의 학생 들 은 빠 른 정렬 알고리즘 을 파악 한다.