[알고리즘] 정렬 ( Sort )

 

◇  설명

-  데이터(원소)들을 어떤 기준에 따라 순서를 정해 열거

	종류
O(n²)	버블 정렬  ( Bubble Sort )
	선택 정렬  ( Selection sort )
	삽입 정렬  ( Insertion sort )
O(n log n)	병합/합병 정렬  ( Merge sort )
	힙 정렬  ( Heap sort )
	퀵 정렬  ( Quick sort )
	트리 정렬  ( Tree sort )
하이브리드 정렬	팀 정렬  ( Tim sort )
	블록 병합 정렬  ( Block merge sort )
	인트로 정렬  ( Intro sort )
그 밖에	기수 정렬  ( Radix sort )
	카운팅 정렬  ( Counting sort )
	셸 정렬  ( Shell's sort )
	보고 정렬  ( Bogo sort, stupid sort )
	보고보고 정렬  ( Bogobogo sort )
	대기 정렬  ( Sleep sort )
	중력 정렬  ( Gravity sort )
안정 정렬

 

◇  코드

 ∎  선택 정렬  

import java.util.Scanner;

public class Sort_01_selection {
	
	public static void selectionSort( int a[] ) {
		int idx, tmp, n = a.length;
		for( int i = n-1; i >= 0; i-- ) {
			idx = 0;
			for( int j = 0; j <= i; j++ )
				if( a[idx] < a[j] ) 
					idx = j;
			tmp = a[idx];
			a[idx] = a[i];
			a[i] = tmp;
		}
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int i, n = sc.nextInt();
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
        sc.close();    
		
		selectionSort( a );
		
		for( int r : a )
			System.out.println(r);

	}
}

 

 ∎  버블 정렬

import java.util.Scanner;

public class Sort_02_bubble {

	public static void bubbleSort( int a[] ) {
		int tmp, n = a.length;
		for( int i = n-1; i >= 1; i-- ) {
			for( int j = 0; j <= i-1; j++ ) {
				if( a[j] > a[j+1] ) {
					tmp = a[j];
					a[j] = a[j+1];
					a[j+1] = tmp;
				}
			}
		}
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int i, n = sc.nextInt();
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
		sc.close();
		
		bubbleSort( a );
		
		for( int r : a )
			System.out.println(r);

	}
}

 

 ∎  삽입 정렬

import java.util.Scanner;

public class Sort_03_insertion {
	
	public static void insertionSort( int a[] ) {
		int i, tmp, loc;
		for( i = 1; i < a.length; i++ ) {
			loc = i-1;
			tmp = a[i];
			while( loc >= 0 && tmp < a[loc] ) {
				a[loc+1] = a[loc];
				loc--;
			}
			a[loc+1] = tmp;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int i, n = sc.nextInt();
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
		sc.close();
		
		insertionSort( a );
		
		for( int r : a )
			System.out.println(r);

	}
}

 

 ∎  합병 정렬

import java.io.*;

public class Sort_04_merge {
					
	static void mergeSort( int a[], int s, int e ) {  // s - start, e - end, m - mid
		int m;
		if( s < e ) {
			m = (int)( ( s + e ) / 2 );
			mergeSort( a, s, m );
			mergeSort( a, m+1, e );
			merge( a, s, m, e );
		}
	}
	
	static void merge( int[] a, int s, int m, int e ) {
		int i = s, j = m+1, t = s;
		int tmp[] = new int[a.length];
		while( i <= m && j <= e ) {
			if( a[i] <= a[j] )
				tmp[t++] = a[i++];
			else
				tmp[t++] = a[j++];
		}
		while( i <= m )
			tmp[t++] = a[i++];
		while( j <= e )
			tmp[t++] = a[j++];
		i = s; t = s;
		while( i <= e )
			a[i++] = tmp[t++];
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int i, n = Integer.parseInt( br.readLine() );
		int a[] = new int[n];
		for( i = 0; i < n; i++ ) 
			a[i] = Integer.parseInt( br.readLine() );
		
		mergeSort( a, 0, n-1 ); // a.length-1
		
		for( int r : a )
			bw.write( r + "\n");
		
		bw.flush();
		bw.close();
	}
}

 

 ∎  퀵 정렬

import java.util.Scanner;

public class Sort_05_quick {

	public static void quickSort( int a[], int s, int e ) {	
		int p;  e -= 1;
		if( s < e ) {
			p = partition( a, s, e );
			quickSort( a, s, p-1 );
			quickSort( a, p+1, e );
		}
	}
	
	public static int partition( int a[], int s, int e ) {
		int i, x, tmp;
		x = a[e];
		i = s-1;
		for( int j = s; j <= e-1; j++ ) {
			if( a[j] <= x ) {
				i++;
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}				
		}
		tmp = a[i+1];
		a[i+1] = a[e];
		a[e] = tmp;
		return i+1;
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int i, n = sc.nextInt();
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
		sc.close();
		
		quickSort( a, 0, n );		// 0 ~ n-1
		
		for( int r : a )
			System.out.println(r);

	}
}

 

 ∎  힙  정렬

최소힙  ( 오름차순 )

import java.io.*;

public class Sort_06_heap_min {
	
	static void buildHeap( int a[], int n ) {
		for( int i = (int)(n/2); i >= 0; i-- ) 
			heapify( a, i, n-1 );
	}

	static void heapify( int a[], int k, int n ) {
		int left = 2*k, right = 2*k+1;
		int bigger, tmp;
		if( right <= n ) {
			if( a[left] > a[right] )
				bigger = left;
			else
				bigger = right;
			
		}
		else if( left <= n )
			bigger = left;
		else return;
		if( a[bigger] > a[k] ) {
			tmp = a[k];
			a[k] = a[bigger];
			a[bigger] = tmp;
			heapify( a, bigger, n-1 );
		}
	}

	static void heapSort( int a[], int n ) {
		int tmp;
		buildHeap( a, n );
		for( int i = n-1; i >= 1; i-- ) {
			tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			heapify( a, 0, i-1 );
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int i, n = Integer.parseInt( br.readLine() );
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = Integer.parseInt( br.readLine() );
		
		heapSort( a, n );	// min heap -- asc		// 0 ~ n-1
		
		for( int r : a ) 
			bw.write( r + "\n" );
			
		bw.flush();
		bw.close();	
	}
}

 최대힙 ( 내림차순 )

import java.io.*;

public class Sort_06_heap_max {
	
	static void buildHeap( int a[], int n ) {
		for( int i = (int)(n/2); i >= 0; i-- ) 
			heapify( a, i, n-1 );
	}
	static void heapify( int a[], int k, int n ) {
		int left = 2*k, right = 2*k+1;
		int smaller, tmp;
		if( right <= n ) {
			if( a[left] < a[right] )
				smaller = left;
			else
				smaller = right;
		}
		else if( left <= n )
			smaller = left;
		else return; // a;
		if( a[smaller] < a[k] ) {
			tmp = a[k];
			a[k] = a[smaller];
			a[smaller] = tmp;
			heapify( a, smaller, n-1 );
		}
	}
	static void heapSort( int a[], int n ) {
		int tmp;
		buildHeap( a, n );
		for( int i = n-1; i >= 1; i-- ) {
			tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			heapify( a, 0, i-1 );
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int i, n = Integer.parseInt( br.readLine() );
		int a[] = new int[n];
		for( i = 0; i < n; i++ ) 
			a[i] = Integer.parseInt( br.readLine() );
		
		heapSort( a, n );	// max heap -- desc
		
		for( int r : a ) 
			bw.write( r + "\n" );
			
		bw.flush();
		bw.close();	
	}
}

 

 ∎  기수 정렬

import java.util.Scanner;

public class Sort_07_radix_stable {
	
	public static void radixSort( int a[] ) {
		int i, max = 0, len, n = a.length;
		String s[] = new String[n];
		for( i = 0; i < n; i++ ) {
			len = String.valueOf(a[i]).length();
			//len = (int)(Math.log10(a[i])+1);
			if( max < len )
				max = len;
		}
		for( i = 0; i < n; i++ )
			s[i] = String.format( "%0"+max+"d", a[i] );
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int i, n = sc.nextInt();
		int a[] = new int[n];
		for( i = 0; i < n; i++ )
			a[i] = sc.nextInt();
		sc.close();
		
		radixSort( a );
		
		for( int r : a )
			System.out.println(r);

	}
}

 

 ∎  계수 정렬

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Sort_08_counting {
	
	public static void countingSort( int a[], int b[], int c[] ) {
		int i;
		for( i = 1; i < c.length; i++ )
			c[i] = 0;
		for( i = 0; i < a.length; i++ ) 
			c[a[i]]++;
		for( i = 2; i < c.length; i++ )
			c[i] = c[i] + c[i-1];
		for( i = a.length-1; i >= 0; i-- ) {
			b[c[a[i]]-1] = a[i];
			c[a[i]]--;
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int i, n = Integer.parseInt( br.readLine() );
		int a[] = new int[n];
		int b[] = new int[n];
		int c[] = new int[10001];
		for( i = 0; i < n; i++ ) 
			a[i] = Integer.parseInt( br.readLine() );
		
		countingSort(a, b, c);
		
		for( int r : b ) 
			bw.write( r + "\n");

		bw.flush();
		bw.close();
	}
}

 

◇  출처

  -  설명  --  나무위키
  -  코드  --  쉽게 배우는 알고리즘 ( 문병로 ), 여기저기