[HackerRank]快速排序1─劃分(Quicksort 1 - Partition)

題目描述

給定一個陣列ar和一個支點p,p=ar[0],並將陣列ar依據支點p劃分為left(左邊)、right(右邊)或是equal(相等)。left為小於支點p的所有元素,right為大於支點p的所有元素,equal為等於支點p的所有元素(包含支點p)。

原題網址

https://www.hackerrank.com/challenges/quicksort1

輸入格式

輸入第一行為一個整數n,範圍在1到1000之間(包含1和1000)。

第二行為n個用空格分隔的整數,範圍在-1000到1000之間(包含-1000和1000),不會重複。

輸出格式

輸出只有一行,依序輸出劃分之後left、equal、right這三個集合中的元素,以空格分隔。

範例輸入

5
4 5 3 7 2

範例輸出

3 2 4 5 7

額外解釋

支點p是3。比3小的元素會被分到left集合,等於3的元素會被分到equal集合,比3大的元素會被分到right集合。

因此劃分之後,

left = [2]

equal = [3]

right = [4, 5, 7]

所以會輸出「2 3 4 5 7」。

解題概念

劃分(divide)是快速排序法的一個很重要的概念,可以將一個大問題拆解成小問題。有關於快速排序法的詳細介紹,可以參考這篇文章:

https://magiclen.org/sorting-algorithm/

若要達成這個題目的需求,因為元素不會重複,可以知道equal集合只會有支點p本身,所以可以只另外建立出left和right集合來儲存比大小之後的結果。又由於支點p已經固定好是在索引0的位置,因此只要從索引1開始,把陣列索引1之後的元素都與支點p進行大小比對,把結果存入left和right集合中。最後再把left、支點p和right集合串接在一起輸出即可。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章