버블정렬
-
[프로그래머스] 문자열 내 마음대로 정렬하기알고리즘/프로그래머스 2020. 2. 13. 20:57
문제 설명 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다. 제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. 입출력 예 strings n return [sun, bed, car] 1 [car..
-
[간단 정리] 정렬 알고리즘(버블, 선택, 삽입)컴퓨터 과학/자료구조와 알고리즘 2019. 11. 26. 19:44
*오름차순 기준입니다 1. 버블정렬 첫 번째 자료부터 마지막 자료까지 인접한 자료끼리 비교해가면서 교환한다. 정렬이 되어 있지 않은 자료를 기준으로(최악) 최초에 n-1번, 그다음에 n-2번, 그다음에 n-3번, 이렇게 해서 최대 횟수는 1 + 2 + .. + (n-1) = n(n-1)/2이므로 시간복잡도는 O(N^2)이다. 최고, 평균, 최악의 경우 모두 O(N^2). 구현은 매우 간단하고 성능이 안 좋다. 교환할 때마다 3번의 임시복사가 일어나기 때문이다. >>구현 #include #include void BubbleSort(int arr[], int size); void Swap(int& value1, int& value2); void PrintArr(int arr[], int size); int ..