이번에는 QuickSort Interview Question에 대한 내용 입니다.
앞으로는 코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!
영어 공부는 왕도는 없습니다. 매일 꾸준히 듣고 말하기 연습 하는 것이 가장 중요합니다.
개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.
공부하는 3단계 방법은 아래와 같습니다.
1분 분량을 번역
전체 듣기 두번
문장 듣고 따라 말하기 두번
한국말로 듣고 영어로 말하기
하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
*** 개발자 매일 영어는 제가 개인적으로 공부하기 위해 만든 mp3파일을 혹시 다른 분에게도 도움이 될까 해서 공유하고 있는 것입니다. 부족한 영어 실력으로 번역한 것이라 잘못되었을 수도 있습니다. 이상한 부분은 댓글로 알려 주시면 감사하겠습니다. ***
mp3 파일 다운로드: https://drive.google.com/open?id=15vhlLRvQJPH7jLWTOPwZSwbl_8g9ieeb
원본:
----- mp3 script -----
So now the next question is, how efficient is
this sorting algorithm? Well in an ideal world in quicksort we're dividing the
array in half each time. We pick a great pivot that really is roughly the median
and then half the elements get pivoted to one side of the array and half of them get pivoted
to the other, and then we just apply quicksort to each half. In that case we
get an n log n runtime. One quick and dirty way of seeing why this is n log n
in the good case is that each element is in, gets quicksort called on it,
log n times, and each one of those was one swap, so there's n elements and they
go through log n swaps, then I'll take n log n time overall. However in the bad
case let's imagine what happens here. We pick a really bad pivot, like every time
we pick the pivot element it happens
to be the very first element in the array or the very lowest element in that
subarray. Then we actually have n squared calls to quicksort and therefore our
runtime degenerates to O of n squared. But as long as we're smart about how we pick
the pivot element we can get a pretty efficient runtime and that's
why we typically implement quicksort in the real world. So now that you've seen
how quick sort works at a high level, let's turn to the implementation.
----- 번역 예 -----
이제 다음 질문은 이 소팅알고리즘이 얼마나 효율적이냐입니다. 이상적인 퀵소트는 배열을 매번 반씩 나눌 수 있습니다. 대략 중간에 해당하는 중심값을 선택하고 배열을 반씩 나누고 또 각각의 반에 퀵소트를 적용하면 됩니다. 이 경우 우리는 n log n의 실행시간을 얻을 수 있습니다. 왜 n log n인지 잠깐 보면 각각의 요소에 퀵소트를 적용하면 log n이고 각각 한번의 교환이 필요하여 n 요소들은 log n의 교환을 하고 전체적으로 n log n이 걸릴 것입니다.
나쁜 경우를 생각해봅시다. 매번 첫번째 요소나 하위배열의 아주 낮은 나쁜 중간값을 선택합니다. 결국 n제곱번 큇소트를 호출하여 O n 제곱을이라는 나쁜 실행속도가 됩니다. 그렇지만 잘 좋은 중간값을 뽑는다면 꽤 좋은 효율적 실행시간을 얻을 수 있고 실제 우리가 퀵소트를 그렇게 구현하고 있습니다. 자 여러분은 어떻게 퀵소트가 동작하는지 대락봤습니다. 한번 구현해 봅시다.
----- 이주의 Interview Question (같이 풀어 봐요!) -----
Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
원본문제 링크: https://leetcode.com/problems/kth-largest-element-in-an-array/description/