Overview of QuickSort

Targets

• Developers who are advanced beginner or intermeditate
• People who want to know how quick sort works
• People who are struggling to from performance of your sorting program.

Why I wrote this blog

This blog is for my brain organizing about quick sort.

I have written programs for a long time, but I have not cared data structres and I always rely on libraries, which means I do not understand what data structures are and how algorithms are implemented are.

But now, I am going to Code Chrysalis that teaches us basical programming, how program works and many fundamentals of IT skills. In Code Chrysalis, I am learning Data Structures, Time Complexities, Sort Algorithms and so on.

I had a oppotunity to write quick sort from scratch there.

Why quick sort is good

There are many sort algorithms. I picked up two of them. one is quick sort, the other one is bubble sort. But I do not explain what bubble sort is in this article. If you want to know what bubble sort is, you can access recources I prepared at the end of this article.

• Quick Sort
• Bubble Sort

Comparison of Complexity (resource: Big-O Cheat Sheet)

Second pictures above says that average time complexities of quick sort and bubblesort are like following.

• Quick Sort : O(n log n)
• Bubble Sort : O(n²)

You can see how complexities are different between O(n log n) and O(n²). O(n²) takes so much time if there are large amounts of elements. To avoid that problem, we should use better Complexity. In this case, that is quick. You should think about your program performance.

Algorithm of QuickSort

Quick Sort uses an algorithm called "Divide and conquer algorithms".

"Divide and conquer algorithms" take following 4 steps.

1. To divide one problem into small 2 problems to solve it.
2. To divide each small problem into smalle problems.
3. To continue step 1 and 2 until we can not divide anymore.
4. To combine all small problems that are solved.

I will explain above 4 steps next section with a image.

Processes of QuickSort (resource: Overview of quicksort)

Here, as an example, let's assume that you have an array storing ten random numbers.

We pick up one value called "Pivot" from this array and separate other values to two arrays called "Left" and "Right".
In "Left" array, we put values that are less than or equal to "Pivot", on the other hand, greater values than "Pivot" go into "Right" array. (We "divided" one array into two smaller array. Remember "Divide and conquer algorithms".)

In this article, we always pick rightmost value in the array as a "Pivot".

This dividing process is continued unitil when we can not divide it anymore.

Let's use an image to be able to imagine how the processes are going easily.

Step 1

To pick up one value as a "Pivot" from an array and divide other values into 2 groups called "Left" and "Right".

Step 2

In this image, 6 is selected as a "Pivot".
The numbers below 6 go to the group on the "Left"
The numbers greater than 6 are put into the "Right" group.

Step 3

From Step 2, 3 is selected as a Pivot in Left Group. In Right one, 11 is selected as a "Pivot".
process of each group is like followings.

• Group Left
  • The numbers below 3 go to the group on the "Left"
  • The numbers greater than 3 are put into the "Right" group.
• Group Right
  • The numbers below 11 go to the group on the "Left"
  • The numbers greater than 11 are put into the "Right" group.

Step 4

In Step 3, divinding process will be finished because we can not divide anymore in Group Left.
In Group Right, we continue this process until the end like Group Left is finished.

Step5 and 6

Group Right is also finished same as Group Left.
You can see sorted value now.

Conclusion

• Quick Sort uses "Divide and conquer algorithms".
• "Divide and conquer algorithms" is to divide one large problem into two smaller problems and continue same thing until the end.
• To continue this process, we use recuisive function in a programming code.

In the last, I will finish this article with a quick sort function code in JavaScript.

function quickSort(sourceArray) {
  if(sourceArray.length === 0) {
    return [];
  }

  // copy array to avoid modifying original array
  const copiedSourceArray = sourceArray.slice();
  // store values that are less than or equal to pivot
  let leftArray = [];
  // store values that are greater than pivot
  let rightArray = [];

  // get pivot from rightmost in an array
  const pivot = copiedSourceArray.pop();

  copiedSourceArray.forEach((value) => {
    if(value <= pivot) {
      leftArray.push(value);
    } else {
      rightArray.push(value);
    }
  });

  // continue dividing arrays until the end
  if(leftArray.length > 0) {
    leftArray = this.quickSort(leftArray, recuirsiveCount);
  }
  if(rightArray.length > 0) {
    rightArray = this.quickSort(rightArray, recuirsiveCount);
  }

  return leftArray.concat(pivot, rightArray);
}

resources

• Overview of quicksort
• Divide and conquer algorithms
• Big-O Cheat Sheet
• Quicksort algorithm (Youtube)
• Bubble sort algorithm (Youtube)
• Code Chrysalis

Fundamental knowledge of Stack

Purpose of this blog

The goal of this article is to understand how program works. I will write 3 basic concepts of programming, which are Stack, Heap and Queue, to comprehend process.

In this article, I am going to write Stack

Knowledge you may get after reading this article

• What stack is.
• How stack works (FILO: First IN Last Out).
• Understanding limit of stack.

What is stack?

The image you can see above describes roles of Stack, Heap and Queue. I am not going to explain What heap and queue are in this article.

Meaning in dictionary written.

a pile of things arranged one on top of another

Image of stack (piled books)

We piled books from bottom to top and take a top book out when we want to get bottom one.

Stack in programming is also same like pilied books. When we try to call some tasks, the tasks are stacked in called order and then finishing tasks from top to bottom. we call that process Fisrt In Last Out (FILO).

Example code and process flow

function firstCalledFuncion() {
  console.log('start firstCalledFuncion');

  secondCalledFuncion(); // stacked 2

  console.log('end firstCalledFuncion');
}

function secondCalledFuncion() {
  console.log('start secondCalledFuncion');

  thirdCalledFuncion(); // stacked 3

  console.log('end secondCalledFuncion');
}

function thirdCalledFuncion() {
  console.log('start thirdCalledFuncion');
  console.log('end thirdCalledFuncion');
}

firstCalledFuncion(); // stacked 1

output of above code.

In this program, 3 functions are defined whose names are firstCalledFuncion, secondCalledFuncion and thirdCalledFuncion from top to bottom and called firstCalledFunction in the last part.

Process 1

In last part, We call firstCalledFunction. That means firstCalledFunction is stacked in the stack and execute it.

Process 2

In the process of firstCalledFunction, secondCalledFuncion is called so secondCalledFuncion is piled in the stack.
Note that firstCalledFunction is still not finished so secondCalledFuncion is on firstCalledFunction.
This means that highest priority function is secondCalledFuncion.

Process 3

Here, Same as Process 2.

Process 4

thirdCalledFuncion does not call any function in itself. The process of thirdCalledFuncion proceeds untill the end of it. After finishing process, thirdCalledFuncion is taken out from the stack.

Process 5

After Process 4, secondCalledFunction is top in the stack. secondCalledFunction process is continued from that of process and then proceeds to the end of secondCalledFunction.

After finishing secondCalledFunction, it is taken out same as Process 4.

Process 6

Same as Process 5.

Process 7

All tasks in the stack are popped, which means the stack has no tasks.

Can we put tasks into a stack Infinitely?

The answer of this question is NO.
You can see the following images to understand that there is limit in a stack.

Function in a below image calls itself. (infinite loop)

When we call infinite loop, process is going to stop because of exceeding limit of stack size.

How many tasks does stack allow us to use？

The answer is that it depends on environments.
Following images are examples on my laptop. Google Chrome, Safari and Node has different limit of stack size.

• Google Chrome: 10444
• Safari: 36241
• Node: 10046

Chrome

Safari

Node.js( on my environment)

Conclusion

What stack is.

• Stack in programming is that it is like TODO tasks.

How stack works (FILO: First IN Last Out).

• Call tasks, which are functions, from top to bottom.
• If you call infinite loop, error occurs because of exceeding limit of stack size.

Understanding limit of stack.

• Stack does not allow us to call function infinitely in one process.
• The number of tasks that a stack can have is that it depends on envronments.

Reference

• Concurrency model and Event Loop
• Cambridge Dictionary
• [フリー写真] 積み重ねた本