데이터 구조 - 정렬 알고리즘 (기초)

1, 직접 삽입 정렬
/*    */
void insertion_sort (element arr[], int n) {
	int i,j;
	element next;
	for(i = 1; i<n; i++) {
		/*      */
		next = arr[i];
		/*      next      */
		for(j = i-1; j>=0 && next<arr[j]; j--) {
			arr[j+1] = arr[j];
		}
		/*  */
		arr[j+1] = next;
	}
}

2. 힐 정렬 (삽입)
<span style="font-size:14px;">void shell_sort(element arr[], int n) {
	int i, j;
	int dis = n/2;
	while(dis >= 1) {
		for(i = dis; i<n; i++) {
			element next = arr[i];
			//next   ,       ,   next            
			for(j = i - dis; next<arr[j] && j>=0; j = j-dis) {
				arr[j+dis] = arr[j];
			}
			arr[j+dis] = next;
		}
		dis /= 2;
	}
}</span>

3. 거품 정렬 (교환)
void bubble_sort(element arr[], int n) {
	int i, j;
	for(i = 0; i<n; i++) {
		for(j = 0; j<n-i-1; j++){
			if(arr[j]>arr[j+1]) {
				arr[j] = arr[j] + arr[j+1] - (arr[j+1] = arr[j]);
			}
		}
	}
}

4. 빠 른 정렬 (교환)
/*    (  )*/
void quick_sork(element arr[] ,int left ,int right) {
	int i, j;
	element pivot, temp;
	
	if(left < right) {
	   //i     ,j     
		i = left;
		j = right;
		//          
		pivot = arr[left];
		/*
			1.          pivot   
			2.          pivot   
			3.  i<j      
		*/
		do {
			do
				i++;
			while(arr[i]<pivot);
			
			do 
				j--;
			while(arr[j]>pivot);
			
			if(i<j){
				arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
			}
		}while(i < j);
		// pivot    j
		arr[left] = arr[left] + arr[j] - (arr[j] = arr[left]);
		/*
			             pivot           pivot
			1.left,j-1
			2.j+1,right
		*/
		quicksork(arr, left, j-1);
		quicksork(arr, j+1, right);
	}
}

5. 정렬 선택
/*    */
void select_sort(element arr[], int n) {
	int i, j;
	int min;
	for(i = 0; i<n; i++) {
		min = i;
		//        
		for(j = i+1; j<n; j++) {
			if(arr[min]>arr[j]) {
				min = j;
			}
		}
		//            ,         
		arr[i] = arr[i] + arr[min] - (arr[min] = arr[i]);
	}
}

좋은 웹페이지 즐겨찾기