컴퓨터 알고리즘 초급 #6 ( 퀵 정렬 in c )
2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 힙 정렬 힙 정렬이란? - 힙의 특성을 이용한 정렬 수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙이란 ? - 완전 이진 트리에 가까운 형태 이진 트리란? - 각 �� 15051015.tistory.com 퀵 정렬 (Quicksort) : 피봇이라는 값을 기준으로 피봇보다 작은것은 왼쪽, 큰것은 오른쪽으로 보내는 파티셔닝이라는 작업을 반복해서 작은 숫자는 계속 왼쪽, 큰 숫자는 계속 오른쪽으로 보내서 정렬시키는 방법 Divide-and-Conquer paradigm을 사용 (작게 쪼개서 작은걸..
합병 정렬 알고리즘 합병 정렬이란? - 합병을 이용한 알고리즘 합병이란? - 두개를 합치는 것 무엇을 합병할 것인가? 두개의 정렬된 배열을 하나의 배열로 합병 입력 : n개의 숫자 출력 : 정렬된 n 개의 숫자 ( 오름 차순 ) ex ) 배열 1 : 배열 2 : -> 결과 : Point : 두 정렬은 이미 정렬이 되어 있다. 알고리즘 : 배열 1과 배열 2의 첫번째 숫자를 비교해서 저 작은걸 결과의 첫번째에 넣어준다. 여기서는 배열 1의 첫번째 숫자 (1) 이 더 작으므로 1을 넣는다. 그 후 더 작았던 배열 1의 첫번째 숫자를 삭제한다. 그 후 배열 1의 첫번째 자리와 배열2의 첫번째 자리를 비교하는 작업을 반복한다. Step0 : 배열 1 : 배열 2 : -> 결과 : Step1 : 배열 1 : 배열..
정렬 문제 ( 오름차순 내림차순 ) 입력 - n개의 숫자들의 배열이다. 출력 - 입력된 숫자의 배열이 크기순을 조건으로 만족하도록 나열한 결과 선택정렬 알고리즘 선택정렬은 무엇인가? - 선택해서 정렬하는 알고리즘이다. 선택을 할때 무엇을 선택하는지가 중요한 핵심이 된다. 1. 최소값 선택 정렬 (결과 : 오름차순) 2. 최대값 선택 정렬 (결과 : 내림차순) 최소값 선택 정렬의 알고리즘 1. 정렬되지 않는 숫자 중 가장 작은 숫자 선택 ( 최소값 ) 2. 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 최소값이 가장 앞으로감 3. 첫번째를 제외하고 그 뒤에서부터 정렬되지 않은 숫자들 중 가장 작은 숫자 선택, 가장 앞 +1 로 보냄 4. 반복 ex) 5 , 4 , 2 , 1, 3 첫..