Commit170eda0

committed

iluwatar#1 Add quicksort snippet

1 parent3faaeb9 commit170eda0Copy full SHA for 170eda0

File tree

+87

-0

lines changed

+87

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,6 +9,9 @@ Update the sample application with the snippet and add a test for it. After prov`
`9`	`9`
`10`	`10`	`##Table of Contents`
`11`	`11`
	`12`	`+###Algorithm`
	`13`	`+*[Quicksort](#quicksort)`
	`14`	`+`
`12`	`15`	`###Array`
`13`	`16`	`*[Generic two array concatenation](#generic-two-array-concatenation)`
`14`	`17`	`*[Generic N array concatenation](#generic-N-array-concatenation)`
`@@ -33,6 +36,41 @@ Update the sample application with the snippet and add a test for it. After prov`
`33`	`36`	`*[Reverse string](#reverse-string)`
`34`	`37`	`*[String to date](#string-to-date)`
`35`	`38`
	`39`	`+##Algorithm`
	`40`	`+`
	`41`	`+###Quicksort`
	`42`	`+`
	`43`	+```java
	`44`	`+publicstaticvoid quickSort(int[] arr,int left,int right) {`
	`45`	`+int pivotIndex= left+ (right- left)/2;`
	`46`	`+int pivotValue= arr[pivotIndex];`
	`47`	`+int i= left, j= right;`
	`48`	`+while (i<= j) {`
	`49`	`+while (arr[i]< pivotValue) {`
	`50`	`+ i++;`
	`51`	`+ }`
	`52`	`+while (arr[j]> pivotValue) {`
	`53`	`+ j--;`
	`54`	`+ }`
	`55`	`+if (i<= j) {`
	`56`	`+int tmp= arr[i];`
	`57`	`+ arr[i]= arr[j];`
	`58`	`+ arr[j]= tmp;`
	`59`	`+ i++;`
	`60`	`+ j--;`
	`61`	`+ }`
	`62`	`+if (left< i) {`
	`63`	`+ quickSort(arr, left, j);`
	`64`	`+ }`
	`65`	`+if (right> i) {`
	`66`	`+ quickSort(arr, i, right);`
	`67`	`+ }`
	`68`	`+ }`
	`69`	`+ }`
	`70`	+```
	`71`	`+`
	`72`	`+[⬆ back to top](#table-of-contents)`
	`73`	`+`
`36`	`74`	`##Array`
`37`	`75`
`38`	`76`	`###Generic two array concatenation`

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -216,4 +216,37 @@ public static void zipFile(String srcFilename, String zipFilename) throws IOExce`
`216`	`216`	`}`
`217`	`217`	`}`
`218`	`218`	`}`
	`219`	`+`
	`220`	`+/**`
	`221`	`+ * Sort an array with quicksort algorithm`
	`222`	`+ * @param arr array to sort`
	`223`	`+ * @param left left index where to begin sort (e.g. 0)`
	`224`	`+ * @param right right index where to end sort (e.g. array length - 1)`
	`225`	`+ */`
	`226`	`+publicstaticvoidquickSort(int[]arr,intleft,intright) {`
	`227`	`+intpivotIndex =left + (right -left) /2;`
	`228`	`+intpivotValue =arr[pivotIndex];`
	`229`	`+inti =left,j =right;`
	`230`	`+while (i <=j) {`
	`231`	`+while (arr[i] <pivotValue) {`
	`232`	`+i++;`
	`233`	`+ }`
	`234`	`+while (arr[j] >pivotValue) {`
	`235`	`+j--;`
	`236`	`+ }`
	`237`	`+if (i <=j) {`
	`238`	`+inttmp =arr[i];`
	`239`	`+arr[i] =arr[j];`
	`240`	`+arr[j] =tmp;`
	`241`	`+i++;`
	`242`	`+j--;`
	`243`	`+ }`
	`244`	`+if (left <i) {`
	`245`	`+quickSort(arr,left,j);`
	`246`	`+ }`
	`247`	`+if (right >i) {`
	`248`	`+quickSort(arr,i,right);`
	`249`	`+ }`
	`250`	`+ }`
	`251`	`+ }`
`219`	`252`	`}`

Lines changed: 16 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -212,4 +212,20 @@ public void testZipFile() throws IOException {`
`212`	`212`	`Files.deleteIfExists(newFile(dst).toPath());`
`213`	`213`	`}`
`214`	`214`	`}`
	`215`	`+`
	`216`	`+/**`
	`217`	`+ * Tests for {@link Library#quickSort(int[], int, int)}`
	`218`	`+ */`
	`219`	`+@Test`
	`220`	`+publicvoidtestQuickSort() {`
	`221`	`+int[]arr =newint[] {7,13,3,1,8,5};`
	`222`	`+Library.quickSort(arr,0,arr.length -1);`
	`223`	`+assertEquals(arr.length,6);`
	`224`	`+assertEquals(arr[0],1);`
	`225`	`+assertEquals(arr[1],3);`
	`226`	`+assertEquals(arr[2],5);`
	`227`	`+assertEquals(arr[3],7);`
	`228`	`+assertEquals(arr[4],8);`
	`229`	`+assertEquals(arr[5],13);`
	`230`	`+ }`
`215`	`231`	`}`

Comments

(0)