Ankush Bisht's Blog

Sorting : The most common and interesting area in algorithms

2010-02-14T00:46:00.003+05:30

Dear Friends,
I like the sorting algorithms very much and want to share some simplest implementations of sorting algorithms.
1)
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Here is the implementation.
/*
* Main.java
*
* Copyright 2010 Ankush Bisht
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
import java.util.Scanner;
public class Main {
public static void main (String args[]) {
Scanner in=new Scanner(System.in);
System.out.println("Enter number of elements in the array");
int n=in.nextInt();
int a[]=new int[n];
int i,j,temp;
System.out.println("Enter "+n+" numbers");
for(i=0;i<n;i++)
{
a[i]=in.nextInt();
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}
2)
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
* simple implementation
* efficient for (quite) small data sets
* adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
* more efficient in practice than most other simple quadratic (i.e. O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4[citation needed], and the running time is linear in the best case
* stable, i.e. does not change the relative order of elements with equal keys
* in-place, i.e. only requires a constant amount O(1) of additional memory space
* online, i.e. can sort a list as it receives it.
Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
Here is the implementation.
/*
* Insertion.java
*
* Copyright 2010 Ankush
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
import java.util.*;
public class Insertion {
public static void main (String args[]) {
Scanner in=new Scanner(System.in);
int i,key,j,n;
System.out.println("Enter number of elements in the array");
n=in.nextInt();
int []a=new int [n];
System.out.println("Enter "+n+" numbers");
for(i=0;i<n;i++)
{
a[i]=in.nextInt();
}
for(i=1;i<n;i++)
{
key=a[i];
for(j=i-1;j>=0&&a[j]>key;)
{
a[j+1]=a[j];
j--;
a[j+1]=key;
}
}
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}
3)
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.
Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as Insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.
However, one significant advantage that bubble sort has over most other implementations, even QuickSort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. Performance of bubble sort over an already-sorted list (best-case) is O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, Insertion sort also has this mechanism, and also performs better on a list that is substantially sorted (having a small number of inversions).
Here is its implementation
/*
* Main.java
*
* Copyright 2010 Ankush Bisht
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
import java.util.Scanner;
public class Main {
public static void main (String args[]) {
Scanner in=new Scanner(System.in);
int i,temp,j,n,k;
System.out.println("Enter number of elements in the array");
n=in.nextInt();
int []a=new int [n];
System.out.println("Enter "+n+" numbers");
for(i=0;i<n;i++)
{
a[i]=in.nextInt();
}
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
for(k=0;k<n;k++)
System.out.println(a[k]+" ");
}
}
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}
4)
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes Θ(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time. Additionally, QuickSort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that QuickSort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures.
Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort.
Here is its implementation
/*
* Main.java
*
* Copyright 2010 Ankush
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
import java.util.Scanner;
public class Main {
/*This method partitions the array into two halves*/
public static int partition(int a[],int p,int q)
{
int temp;
int i=p;
for(int j=p+1;j<q;j++)
{
if(a[j]<=a[p]) /*a[p] is pivot. Here we are taking first element of the array as pivot*/
{
i=i+1;
temp=a[i]; /*shift elements to left those are less than the pivot and to right those are greater than the pivot*/
a[i]=a[j];
a[j]=temp;
}
}
temp=a[p]; /*shift the pivot to the middle of the array*/
a[p]=a[i];
a[i]=temp;
return i;
}
public static void quickSort(int a[],int p,int q)
{
if(p<q) /*If p=q then there is only one element or no element so the array is already sorted*/
{
int r=partition(a,p,q);
quickSort(a,p,r); /*recursive call to first half*/
quickSort(a,r+1,q); /*recursive call to second half*/
}
}
public static void main (String args[])
{
Scanner in=new Scanner(System.in);
System.out.println("Enter number of elements in the array");
int n=in.nextInt();
int a[]=new int[n];
int i;
System.out.println("Enter "+n+" numbers");
for(i=0;i<n;i++)
{
a[i]=in.nextInt();
}
System.out.println("Array before sorting");
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
quickSort(a,0,n); /*Initial call to method quickSort*/
System.out.println();
System.out.println("Array after sorting");
for(i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}
There are lot more algorithms to go. I will add them later. Please notify me if there is any error or mistake anywhere in my implementation and also if there is a better implementation of the same.

EratosthenesSieve : A very fast algorithm for finding Prime numbers.

2010-02-14T00:23:00.001+05:30

CSS (Style):

Code:

<div class="php">
<ol>
<li class="li1"><div class="de1">
<span class="coMULTI">/*</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      EratosthenesSieve.java</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      </span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      Copyright 2010 Ankush Bisht <ankushbisht18@gmail.com></span></div>
</li>
<li class="li2"><div class="de2">
<span class="coMULTI"> *      </span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      This program is free software; you can redistribute it and/or modify</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      it under the terms of the GNU General Public License as published by</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      the Free Software Foundation; either version 2 of the License, or</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      (at your option) any later version.</span></div>
</li>
<li class="li2"><div class="de2">
<span class="coMULTI"> *      </span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      This program is distributed in the hope that it will be useful,</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      but WITHOUT ANY WARRANTY; without even the implied warranty of</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      GNU General Public License for more details.</span></div>
</li>
<li class="li2"><div class="de2">
<span class="coMULTI"> *      </span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      You should have received a copy of the GNU General Public License</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      along with this program; if not, write to the Free Software</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,</span></div>
</li>
<li class="li1"><div class="de1">
<span class="coMULTI"> *      MA 02110-1301, USA.</span></div>
</li>
<li class="li2"><div class="de2">
<span class="coMULTI"> */</span></div>
</li>
<li class="li1"><div class="de1">
 </div>
</li>
<li class="li1"><div class="de1">
<span class="kw2">public</span> <span class="kw2">class</span> EratosthenesSieve <span class="br0">{</span></div>
</li>
<li class="li1"><div class="de1">
 </div>
</li>
<li class="li1"><div class="de1">
    <span class="kw2">public</span> static void main <span class="br0">(</span>String args<span class="br0">[</span><span class="br0">]</span><span class="br0">)</span> <span class="br0">{</span>       </div>
</li>
<li class="li2"><div class="de2">
        <a href="http://www.php.net/system"><span class="kw3">System</span></a><span class="sy0">.</span>out<span class="sy0">.</span>println<span class="br0">(</span><span class="st0">"Enter the Number till you want to print the Primes"</span><span class="br0">)</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
        int a<span class="br0">[</span><span class="br0">]</span><span class="sy0">=</span><span class="kw2">new</span> int<span class="br0">[</span><span class="kw2">new</span> java<span class="sy0">.</span>util<span class="sy0">.</span>Scanner<span class="br0">(</span><a href="http://www.php.net/system"><span class="kw3">System</span></a><span class="sy0">.</span>in<span class="br0">)</span><span class="sy0">.</span>nextInt<span class="br0">(</span><span class="br0">)</span><span class="br0">]</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
        <span class="kw1">for</span><span class="br0">(</span>int i<span class="sy0">=</span><span class="nu0">0</span><span class="sy0">;</span>i<span class="sy0"><</span>a<span class="sy0">.</span>length<span class="sy0">;</span>i<span class="sy0">++</span><span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
        a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">=</span>i<span class="sy0">+</span><span class="nu0">1</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
        int i<span class="sy0">,</span>j<span class="sy0">,</span>k<span class="sy0">,</span>step<span class="sy0">;</span></div>
</li>
<li class="li2"><div class="de2">
        <span class="kw1">for</span><span class="br0">(</span>i<span class="sy0">=</span><span class="nu0">1</span><span class="sy0">;</span>i<span class="sy0"><</span>a<span class="sy0">.</span>length<span class="sy0">;</span>i<span class="sy0">++</span><span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
        <span class="br0">{</span></div>
</li>
<li class="li1"><div class="de1">
                <span class="kw1">if</span><span class="br0">(</span>a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">!=</span><span class="nu0">0</span><span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
                <span class="br0">{</span></div>
</li>
<li class="li1"><div class="de1">
                k<span class="sy0">=</span>a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">*</span><span class="nu0">2</span><span class="sy0">-</span><span class="nu0">1</span><span class="sy0">;</span></div>
</li>
<li class="li2"><div class="de2">
                step<span class="sy0">=</span>a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
                <span class="kw1">for</span><span class="br0">(</span>j<span class="sy0">=</span>k<span class="sy0">;</span>j<span class="sy0"><</span>a<span class="sy0">.</span>length<span class="sy0">;</span>j<span class="sy0">+=</span>step<span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
                a<span class="br0">[</span>j<span class="br0">]</span><span class="sy0">=</span><span class="nu0">0</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
                <span class="br0">}</span></div>
</li>
<li class="li1"><div class="de1">
        <span class="br0">}</span></div>
</li>
<li class="li2"><div class="de2">
        <a href="http://www.php.net/system"><span class="kw3">System</span></a><span class="sy0">.</span>out<span class="sy0">.</span>println<span class="br0">(</span><span class="st0">"Prime Numbers between 1 and 100 are: "</span><span class="br0">)</span><span class="sy0">;</span></div>
</li>
<li class="li1"><div class="de1">
        <span class="kw1">for</span><span class="br0">(</span>i<span class="sy0">=</span><span class="nu0">0</span><span class="sy0">;</span>i<span class="sy0"><</span>a<span class="sy0">.</span>length<span class="sy0">;</span>i<span class="sy0">++</span><span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
        <span class="br0">{</span></div>
</li>
<li class="li1"><div class="de1">
            <span class="kw1">if</span><span class="br0">(</span>a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">!=</span><span class="nu0">0</span><span class="br0">)</span></div>
</li>
<li class="li1"><div class="de1">
            <a href="http://www.php.net/system"><span class="kw3">System</span></a><span class="sy0">.</span>out<span class="sy0">.</span>println<span class="br0">(</span>a<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">+</span><span class="st0">" "</span><span class="br0">)</span><span class="sy0">;</span></div>
</li>
<li class="li2"><div class="de2">
        <span class="br0">}</span></div>
</li>
<li class="li1"><div class="de1">
    <span class="br0">}</span></div>
</li>
<li class="li1"><div class="de1">
<span class="br0">}</span></div>
</li>
</ol>
</div>

/*
* EratosthenesSieve.java
*
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
public class EratosthenesSieve {
public static void main (String args[]) {
System.out.println("Enter the Number till you want to print the Primes");
int a[]=new int[new java.util.Scanner(System.in).nextInt()];
for(int i=0;i<a.length;i++)
a[i]=i+1;
int i,j,k,step;
for(i=1;i<a.length;i++)
{
if(a[i]!=0)
{
k=a[i]*2-1;
step=a[i];
for(j=k;j<a.length;j+=step)
a[j]=0;
}
}
System.out.println("Prime Numbers between 1 and "+a.length+" are: ");
for(i=0;i<a.length;i++)
{
if(a[i]!=0)
System.out.println(a[i]+" ");
}
}
}