정렬 - 버블정렬 (Bubble sort)

버블정렬

서로 인접한 두 원소를 비교하여 정렬하는 알고리즘 

- 비교하여 왼쪽이 오른쪽 보다 크다면 둘이 바꿈.(왼쪽->오른쪽)

 

unsortedPartitionIndex =  the last index of the unsorted partition

i = index used to traverse the array from left to right 

 

bubble sort

 

특징

- 구현이 간단하다

- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

 

시간복잡도

비교 횟수
최상, 평균, 최악 모두 일정
n-1, n-2, … , 2, 1 번 = n(n-1)/2

교환 횟수
입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.

 in-place algorithm (don't need extra memories)

O(n2) time complexity - quadratic

it will take 100 steps to sort 10 times, 10000 steps to sort 100 items 

algorithm degrades quickly

stable sort algorithm

 

 

pubilc static void main(String[] args){

	int[] intArray = [20, 35, -10, 8, 54, 1, -22];
    
    for(int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0; lastUnsortedIndex --){
    	for(int i = 0; i < lastUnsortedIndex; i++){
        	if(intArray[i] > intArray[i+1]{
            	swap(intArray, i, i+1);
            }
        }
    }
    
  

}

public static void swap(int[] array, int i , int j){

	if(i ==j){
    	return;
    }

    // array[i]와 array[j]의 값을 바꾼다.
	int temp = array[i];
    array[i] = array[j];
    array[j] = temp;


}

 

 

references

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

udemy - data structures and algorithm