패스트캠퍼스 챌린지 9일차

기본 정렬 알고리즘

 공간 복잡도(Space Complexity)

  - 프로그램을 실행 및 완료한느데 필요한 저장공간의 양  - 총 필요 저장 공간   • 고정 공간 : 코드 저장 공간, 단순 변수 및 상수 EX) 코드의 양,줄   • 가변 공간 : 실행 중 동적으로 필요한 공간  EX) for문을 통한 반복 횟수 

 

버블 정렬 (Bubble Sort)

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

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

public class BubbleSort {
  public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
    // 입력한 dataList의 size만큼 돌며 버블 정렬
    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;
  }
}

시간 복잡도 O(n^2)

 

선택 정렬 (Selection Sort)

 - 주어진 데이터 중, 최소값을 찾아서 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다

 - 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

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

public class SelectionSort {
  public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
    int lowest;
    for (int stand = 0; stand < dataList.size() - 1; stand++) {
      lowest = stand;
      for (int index = stand + 1; index < dataList.size(); index++) {
        if (dataList.get(lowest) > dataList.get(index)) {
          lowest = index;
        }
      }
      Collections.swap(dataList, lowest, stand);
    }
    return dataList;
  }
}

시간 복잡도 O(n^2)

 

삽입 정렬 (Insertion Sort)

 - 두 번째 인덱스부터 시작

 - 해당 인덱스 앞에 있는 데이터 부터 비교해 인덱스의 데이터가 더 작으면 데이터를 해당 인덱스 앞으로 이동

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

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

시간 복잡도 O(n^2)

 

 

정렬에 사용되는 3가지 방법을 코드로 구현해 보았다.

정렬은 배열 알고리즘에 기본이 되는 것으로 쉬울 수 있지만 반드시 인지하고 넘어가야 한다

 

9일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]