 Open Access
 Total Downloads : 2009
 Authors : Aayush Agarwal, Vikas Pardesi, Namita Agarwal
 Paper ID : IJERTV2IS50210
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 16052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A New Approach To Sorting: MinMax Sorting Algorithm
Aayush Agarwal 
Vikas Pardesi 
Namita Agarwal 
M.Tech, CDAC Noida 
M.Tech, DTU, Delhi 
B.Tech, BITS, Sonepat 
Abstract
Many algorithms are available for sorting the unordered elements. Most important of them are Bubble sort, Heap sort, Insertion sort and Quick sort. This paper presents the new algorithm for sorting the elements which is based on minimum and maximum elements of the array which results in placing the elements at appropriate position. This will reduce the number of passes in which the sorting takes place. We will examine this sorting technique and compare with the other available sorting algorithms in terms of complexity, memory and other factors.

INTRODUCTION
Sorting has been a profound area for the algorithmic researchers. And many resources are invested to suggest a more working sorting algorithm. For this purpose many existing sorting algorithms were observed in terms of the efficiency of the algorithmic complexity. Since the dawn of computing, the sorting problem has attracted a great deal of research [1]. Till date, Sorting algorithms are open problems and many researchers in past have attempted to optimize them with optimal space and time scale. This paper describes the new sorting algorithm named MinMax Sorting based on minimum and maximum element. This algorithm finds the minimum and maximum element from the array and placed in first and last position of the array. Then it increment the array index from the first position and decrement the array index from the last position, from this we find the new array and from this new array again we find the minimum and maximum element and placed in first and last position of the new array and so on. In this way, number of passes is reduced to sort the number of elements and it also reduces the time which the algorithm takes to sort the numbers.
This paper includes:

Section 2 describes the proposed algorithm.

Section 3 describes the comparative study with the other algorithms.

Section 4 describes the conclusion.


PROPOSED ALGORITHM
The MinMax Sorting Algorithm works on the minimum and maximum element of the array. It finds the minimum and maximum element from the array and set on the first and last position of the array. Then the array index increment from the first position and decrement from the last position to get the new array. From this new array, it again finds the minimum and maximum element and set on their respective positions. In this way, this sorting algorithm sorts the elements of the array.
Here we provide the PseudoCode for this sorting algorithm.
PseudoCode for MinMax Sorting

Set p:=0,q:=n1 //n is the number of elements

while p<q do: Repeat steps 3 to 6

Minimum(a,p,q) //pass array,p,q to find minimum element of current array

Maximum(a,p,q) //pass array,p,q to find maximum element of current array

Set p:=p+1 //increment p

Set q:=q+1 //increment q

End while

Print sorted array //end of algorithm
PseudoCode for finding the minimum element from the array:
PseudoCode for Minimum Function
Minimum(int a[],int p,int q) //Receive array,p,q

Set min:=a[p] //set the first element of array to min

for l=p to q do: Repeat Steps 3 to 5

if a[l]<min then

swap(a[l],min) //swapping is done and find the minimum element

Set l:=l+1;

End for

a[p]=min
PseudoCode for finding the maximum element from the array:
PseudoCode for Maximum Function
Maximum(int a[],int p,int q) //Receive array,p,q

Set max:=a[q] //set the last element of array to min

for i=p to q do: Repeat Steps 3 to 5

if a[i]>max then

swap(a[i],max) //swapping is done and find the maximum element

Set i:=i+1;

End for

max=a[q]
We provide the source code of the MinMax Sorting Technique:
Source Code in C
#include<stdio.h>
#include<conio.h>
void minimum(int a[],int p,int q)
{
int min=a[p]; for(int l=p;l<=q;l++)
{
if(a[l]<min)
{
int temp=min; min=a[l]; a[l]=temp;
}
a[p]=min;
}
for(int i=0;i<n;i++) Scanf("%d",&a[i]); for(int j=0;j<n;j++)
printf("\nYour Array is :%d ",a[j]); printf("\nSorted Array is :");
int p=0,q=n1; while(p<q)
{
minimum(a,p,q);
maximum(a,p,q); p++;
q–;
}
for(int k=0;k<n;k++) printf("%d\n",a[k]); getch();
}
OUTPUT
How many elements you want to enter? 6
23 43 12 54 27 5
Your Array is: 23 43 12 54 27 5
Sorted Array is: 5 12 23 27 43 54

COMPARATIVE STUDY WITH OTHER ALGORITHMS
In this section, we provide the comparison of our MinMax sorting algorithm with others existing sorting algorithms in different cases with example.
}
void maximum(int a[],int p,int q)
{
int max=a[q]; for(int i=p;i<=q;i++)
{
int temp; if(a[i]>max)
{
temp=a[i]; a[i]=a[q]; a[q]=temp;
}
max=a[q];
}
}
void main()
{
Clrscr();
int n,a[20];
printf("\nHow many element you want to enter…?\n");
scanf("%d",&n);

Comparison in terms of Time Complexity with other Algorithms:
NAME
BEST CASE
AVERAGE CASE
WORST CASE
MINMAX SORT
n2
n2
n2
QUICKSORT
nlog n
nlog n
n2
HEAP SORT
nlog n
nlog n
nlog n
MERGE SORT
nlog n
nlog n
nlog n
BUBBLE SORT
n
n2
n2
SELECTION SORT
n2
n2
n2
INSERTION SORT
n
n2
n2
NAME
BEST CASE
AVERAGE CASE
WORST CASE
MINMAX SORT
n2
n2
n2
QUICKSORT
nlog n
nlog n
n2
HEAP SORT
nlog n
nlog n
nlog n
MERGE SORT
nlog n
nlog n
nlog n
BUBBLE SORT
n
n2
n2
SELECTION SORT
n2
n2
n2
INSERTION SORT
n
n2
n2
Table 1: Complexity Comparison

Comparison in Number of Passes to Sort the Elements:
This comparison is shown by taking an example. In this, we have an array of 5 integers andwe are differentiating soring algorithms in terms of number of passes and proved that our algorithm takes minimum number of passes to sort an array. Here we are comparing only with two sorting i.e., Selection sort and bubble sort.
Let us take an example: Array: 5 4 3 2 1
MinMax Sorting:
2, 3, 5, 1, 4 (Given Array)
1, 3, 5, 2, 4 (After Minimum Function)
1, 3, 4, 2, 5 (After MaximumFunction) Pass 1
1, 3, 4, 2, 5 (After Minimum Function)
1, 2, 4, 3, 5 (After Maximum Function) Pass 2
1, 2, 3, 4, 5 Resultant Sorted Array
It will take only two passes to sort the elements. In
General, it takes n / 2 passes to sort the elements where n is the number of elements.
Bubble Sorting:
2, 3, 5, 1, 4 (Given Array)
2, 3, 5, 1, 4
2, 3, 5, 1, 4
2, 3, 1, 5, 4 Pass 1
2, 3, 1, 4, 5
2, 3, 1, 4, 5 (Intermediate Array after Pass 1)
2, 3, 1, 4, 5
2, 1, 3, 4, 5 Pass 2
2, 1, 3, 4, 5
It will take four passes to sort the elements. In General, it takes (n1) passes to sort the elements where n is the number of elements. It takes just double passes to sort the elements compare to Min Max sorting.
Selection Sort:
2, 3, 5, 1, 4 (Given Array)
1, 3, 5, 2, 4 Pass 1
1, 2, 5, 3, 4 Pass 2
1, 2, 3,5, 4 Pass 3
1, 2, 3, 4, 5 Pass 4
It will also take (n1) passes just taking double time compare to MinMax sorting algorithm.

Comparison in terms of other factors:
All the sorting algorithms have two properties on which they follow. Some sorting algorithms follow these properties but some are not. Our sorting algorithm follows these properties which are as follows:

Stable Sorting: A sorting algorithm is called stable if it keeps elements with equal keys in the same relative order in the output as they were in the input [10].
For example, in the following input the two 4's are indistinguishable:
1, 4a, 3, 4b, 2
And so the output of a stable sorting algorithm must be:
1, 2, 3, 4 , 4
2, 1, 3, 4, 5 a b
2, 1, 3, 4, 5 (Intermediate Array after Pass 2)
1, 2, 3, 4, 5
1, 2, 3, 4, 5 Pass 3
1, 2, 3, 4, 5
1, 2, 3, 4, 5
1, 2, 3, 4, 5 (Intermediate Array after Pass 3)
1, 2, 3, 4, 5
1, 2, 3, 4, 5 Pass 4
1, 2, 3, 4, 5
1, 2, 3, 4, 5 (Final Sorted Array after Pass 4)

Inplace Sorting: Inplace algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not inplace is sometimes called notin place or outofplace [11].
Table 2: Comparison in terms of Stable and Inplace Sorting
NAME
STABLE
INPLACE
MINMAX SORT
YES
YES
QUICKSORT
Depends
YES
HEAP SORT
NO
YES
MERGE SORT
YES
NO
BUBBLE SORT
YES
YES
SELECTION SORT
NO
YES
INSERTION SORT
YES
YES


CONCLUSION

This paper describe the new sorting algorithm named MinMax Sorting based on finding the minimum and maximum element of the array and sort the elements. In this way, we are able to reduce the number of passes required to sort the elements in comparison with other sorting algorithms and also able to remove rabbit and turtle problem. In future work we can try to reduce its time complexity then it can be an efficient and effective sorting algorithm.
REFERENCES

John Darlington, Remarks on A Synthesis of Several Sorting Algorithms, Springer Berlin / Heidelberg, pp 225 227, Volume 13, Number 3 / March, 1980.

Talk presented by Dr. Sedgewick , Open problems in the analysis of sorting and searching algorithms, at the Workshop on the probabilistic analysis of algorithms, Princeton, May, 1997.

Dr. D. E. Knuth, The Art of Computer Programming, 3rd volume, "Sorting and Searching, second edition.

J.P. Linderman. "Theory and Practice in the Construction of a Working Sort Routine." Bell System Technical Journal 63, pp.18271843, 1984.

S. Baase, Computer Algorithms: Introduction to Design and Analysis, AddisonWesley Publishing Co., pp. 58132, 1978.

http://en.wikipedia.org/wiki/Sorting_algorithm

Lavore, Robert. Arrays, Big O Notation and Simple Sorting. Data Structures andAlgorithms in Java (2nd Edition) . Sams, 9780672324536.

Savitch, Walter and Carrano, Frank. Arrays. Java: Introduction to Problem Solving and Programming (5th Edition). Prentice Hall, 9780136072256.

Sedgewick, Robert. Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms. Bundle of Algorithms in Java, Third Edition. Addison WesleyProfessional, 9780201775785.

www.algorithmist.com/index.php/Stable_Sort

www.geeksforgeeks.org/forums/topic/inplacesorting