Java-알고리즘 ( bubble sort )

0. 알고리즘 연습 방법

• 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함
  • 모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작

1. 연습장과 펜을 준비합니다
2. 알고리즘 문제를 읽고 분석한 후에,
3. 간단히 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해봅니다.
4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어봅니다.
5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,
6. 각 문장을 코드 레벨로 적습니다.
7. 변수가 코드에 따라 어떻게 변화하는지 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장으로 펜으로 검증합니다.

1. 버블 정렬이란?

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

2. 버블 정렬 연습해 보기

 

• 예: data_list = [1, 9, 3, 2]
  • 1차 로직 적용
    • 1 와 9 비교, 자리바꿈없음 [1, 9, 3, 2]
    • 9 와 3 비교, 자리바꿈 [1, 3, 9, 2]
    • 9 와 2 비교, 자리바꿈 [1, 3, 2, 9]
  • 2차 로직 적용
    • 1 와 3 비교, 자리바꿈없음 [1, 3, 2, 9]
    • 3 와 2 비교, 자리바꿈 [1, 2, 3, 9]
    • 3 와 9 비교, 자리바꿈없음 [1, 2, 3, 9]
  • 3차 로직 적용
    • 1 와 2 비교, 자리바꿈없음 [1, 2, 3, 9]
    • 2 와 3 비교, 자리바꿈없음 [1, 2, 3, 9]
    • 3 와 9 비교, 자리바꿈없음 [1, 2, 3, 9]

3. 버블 정렬 코드화 하기

 

// src/com.company/Sort/BubbleSort.java

package com.company.Sort;

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        for(int index = 0; index < dataList.size() - 1; index++) {
            boolean swap = false;
            for(int index2 = 0; index2 < dataList.size() - 1 - index; index2++) {
                if(dataList.get(index2) > dataList.get(index2 + 1)) {
                    Collections.swap(dataList, index2, index2 + 1);
                    swap = true;
                }
            }
            if(swap == false) {
                break;
            }
        }
        return dataList;
    }
}

package com.company;

import com.company.Sort.BubbleSort;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> testData = new ArrayList<Integer>();
        for (int i = 0; i < 100; i++) {
            testData.add((int) (Math.random() * 100));
        }
        BubbleSort bSort = new BubbleSort();
        bSort.sort(testData);

        System.out.println(testData);
    }
}

임의 난수를 생성하여 배열에 집어 넣은 후, 이를 버블 정렬로 정렬 하는 예시이다.

 

4. 알고리즘 분석

• 반복문이 두 개 O(n^2)
  • 최악의 경우, n * (n - 1) / 2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)