Girl in IT-wolrd

Everything has been downloaded. Quit download loop.

Tag Archives: algo

Sorting in Java

In this section we discuss four different ways to sort data in Java.

Arrays of primitives

An array of primitives is sorted by direct invocation of Arrays.sort method

int[] a1 = {3,4,1,5,2,6};

Arrays of objects

In order to sort an array of abstract object, we have to make sure that objects are mutually comparable. The idea of comparable is extension of equals in a sence than we need to know not only that two objects are not equal but which one is larger or smaller. This is supported by the Comparable interface. This interface contains only one method with the following signature:

	public int compareTo(Object obj);

Read more of this post

[ALGO] Quick sort

Quicksort or partition-exchange sort, is a fast sorting algorithm, which is using divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.
2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Read more of this post

[ALGO] Merge Sort


Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps:

  • Divide the array into two (or more) subarrays
  • Sort each subarray (Conquer)
  • Merge them into one (in a smart way!)

Read more of this post

[ALGO] Insertion Sort

Insertion Sort

To sort unordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (initially empty):

void insertionSort(int[] ar)
   for (int i=1; i ‹ ar.length; i++)
      int index = ar[i]; int j = i;
      while (j > 0 && ar[j-1] > index)
           ar[j] = ar[j-1];
      ar[j] = index;
} }

Example. We color a sorted part in green, and an unsorted part in black. Here is an insertion sort step by step. We take an element from unsorted part and compare it with elements in sorted part, moving form right to left. Read more of this post

[ALGO] Selection Sort

Selection Sort

The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.

The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,

void selectionSort(int[] ar){
   for (int i = 0; i ‹ ar.length-1; i++)
      int min = i;
      for (int j = i+1; j ‹ ar.length; j++)
            if (ar[j] ‹ ar[min]) min = j;
      int temp = ar[i];
      ar[i] = ar[min];
      ar[min] = temp;
} }

Example. Read more of this post

[ALGO] Bubble sort

Bubble Sort

  1. The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.
void bubbleSort(int ar[])
   for (int i = (ar.length - 1); i >= 0; i--)
      for (int j = 1; j ≤ i; j++)
         if (ar[j-1] > ar[j])
              int temp = ar[j-1];
              ar[j-1] = ar[j];
              ar[j] = temp;
   } } } }

Example. Here is one step of the algorithm. The largest element – 7 – is bubbled to the top: Read more of this post