퀵 정렬2 퀵 정렬(Quick sort) 퀵 정렬이란? 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행 수행속도가 매우 빠르다. 설명 임의의 수를 pivot(피봇)이라는 이름으로 기준을 잡는다.(pivot은 중간값이 적절) pivot값을 기준으로 pivot값보다 작은 값은 pivot 앞으로 큰 값은 뒤로 가게 값들의 위치를 바꾼다. 이 과정이 마무리되면 pivot은 중간에 들어가 있게 되어 있다.(중간값이 적절한 자리를 찾음) pivot을 기준으로 좌우로 나누고(분할) 나눠진 리스트에 대해서 다시 1, 2, 3 과정을 반복한다(재귀). 예시 피벗은 p, 리스트 왼쪽.. 2019. 9. 30. Climbing the Leaderboard(해커랭크, Java) 문제링크: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 알고리즘 설명: scores의 랭크들을 rank배열을 만들어 scores값들의 랭크를 관리했고 그 뒤 alice를 받아 scores값들과 비교했고 alice의 값이 scores의 값보다 크면 scores의 rank값을 result 배열(결과값이 들어가는 배열)에 넣었다. 막혔던 지점: 단순히 2중 for문을 가지고 알고리즘을 짰더니 time limit에 .. 2019. 9. 30. 이전 1 다음