Algorithms – Sorting – Quick Sort – Source Code

This article provides the source code for the Quick Sort algorithm discussed in Algorithms – Sorting – Quick Sort post.

The source code is in C++ language and was verified to be working as expected on a x86_64 (64 bit) machine running Ubuntu 11.04.

Continue reading “Algorithms – Sorting – Quick Sort – Source Code”

Advertisements

Algorithms – Sorting – Quick Sort

Quick sort is considered as one of most efficient of all the sorting algorithms. The average case order of growth of quick sort is O (n log n). Though it has to be noted that the worst case order of growth of quick sort is O (n2).

The strategy behind quick sort is to consider one of the  elements in the array as ‘pivot’ and then partition the remaining elements such that all the elements to the left of the ‘pivot’ element are less than or equal ‘pivot’ and all the elements to the right of the ‘pivot’ element are greater than ‘pivot’. This operation is performed recursively until all the elements in the input list are sorted.

Algorithm:

// Input: An array of elements to be sorted denoted by ‘A’ and the size of the array denoted by ‘n’

// Output: In-place sorted array

// Requirement: The contents of the array to be sorted should be comparable with each other i.e. it is expected that relational operations can be applied on the contents of the array.

Continue reading “Algorithms – Sorting – Quick Sort”

Algorithms – Sorting – Insertion Sort

Insertion sort is considered as one of simplest of all the sorting algorithms. The strategy behind insertion sort is to pick up an element from the list and place it at the right position in the list at the end of each iteration.

Algorithm:

//Input: An array of elements to be sorted denoted by ‘A’ and the size of the array denoted by ‘n’

//Output: In-place sorted array

//Requirement: The contents of the array to be sorted should be comparable with each other i.e. it is expected that relational operations can be applied on the contents of the array.

procedure insertionSort (A, n)
for i = 1 to n-1 do
input (A, i, A[i])
done
end

 

Continue reading “Algorithms – Sorting – Insertion Sort”

Data Structures: Key points about a Binary Tree – Part 2

This article is an extension to article ‘Data Structures: Key points about a Binary Tree – Part 1’. Please refer the part 1 blog post in case you find some of terms used in this article quite confusing.

Complete Binary Tree:

  • A complete binary tree of depth ‘d’ is a strictly binary tree all of whose leaves are at level ‘d’.

Example of a complete binary tree of depth 3:

Continue reading “Data Structures: Key points about a Binary Tree – Part 2”

Data Structures: Key points about a Binary Tree – Part 1

I am fond of Data Structures and Algorithms. Most of the data listed below is from my notes that was captured during my study of Data Structures.

My major source of information on Data Structures is the book – ‘Data Structures Using C and C++ (2nd Edition) by Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum’. You can find more information about the book in the References section at the end of this post.


Definition of a Binary Tree (Ref: Data Structures Using C and C++, 2nd Edition):

  • A Binary tree is a finite set of elements that are either empty or partitioned into three disjoint subsets.
  • The first subset contains a single element called ‘Root’ of the tree.
  • The other two subsets are themselves trees called ‘Left’ and ‘Right’ sub trees of the original tree.
  • A ‘left’ or ‘right’ sub tree can be empty.

Example of a Binary Tree:

Continue reading “Data Structures: Key points about a Binary Tree – Part 1”

Bubble Sort – Source Code

Below is a C++ implementation of Bubble Sort. We do not follow Object Oriented Concepts in the below program but do use a few C++ libraries.

This program has been tested on a x86_64 (64 bit) Linux machine for validity.


Key points to remember:

  • The source code below expects an text file named ‘input.txt’ in the same folder where the binary generated by compiling the below code is placed.
  • The input file should contain space separated integer values that would be read by the program and considered as input.
  • The maximum number of input values that can be processed at once is restricted to 100.

Continue reading “Bubble Sort – Source Code”

Sorting Algorithms–Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. The strategy followed by bubble sort is to compare adjacent elements in the input list (e.g. array) and interchange them if they are out of order.

Each time the algorithm passes through the input list, the highest valued element gets positioned at the right place i.e. at the end of the list. This behaviour of bubbling elements to right position after every pass is responsible for naming this sorting technique as ‘Bubble Sort’.

Let us apply the Bubble sort algorithm on a integer array. The concept can be extended to other type of data as well.