Contents

• 빅오 표기법
• 선택 정렬
• 버블 정렬
  
  

---

정렬

데이터를 정렬하는 이유는 원하는 값을 쉽게 찾기 위해서이다.

• 빅오 표기법(Big-O notation)
  • 알고리즘의 시간 복잡도를 나타내는 표기법이며 $O(f(n))$ 으로 나타낸다.
  • 시간 복잡도는 아래 순으로 퍼포먼스를 판단하며 값이 작을 수록 빠른 시간에 결과가 나온다.
    • $O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)$
      
      

선택 정렬 select sort

• 배열의 가장 작은 값을 가지는 인덱스를 찾아서 가장 작은 값을 앞에서부터 채워나가며 정렬하는 방식
• 시간 복잡도 : $O(n^2)$
• java로 구현하기

    int[] arr = {8, 4, 6, 3, 5, 9, 1};
  
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            // 맨 처음 index 부터 마지막 index까지 모든 값을 비교한다.
            if (arr[i] > arr[j]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
  

  
  
  

버블 정렬 bubble sort

• 처음부터 끝까지 모든 데이터를 비교하면서 가장 큰 수를 맨 뒤로 보내는 정렬
• 시간 복잡도 : $O(n)$
• java로 구현하기

    int[] arr = {8, 4, 6, 3, 5, 9, 1};
  
    for (int i = arr.length - 1; i > 0 ; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }