CareerCup

find the index (k) of the smallest number within the [0..n) (excluding n) and put the smallest number at the last position
find the index (k) of the smallest number within the range [0..n-1) and put the smallest number at the last position
...
find the index (k) of the smallest number within the range [0..n-i) and put the smallest number at the last position
...
find the index (k) of the smallest number within the range [0..1) and put the smallest number at the last position

Time: O(n^2)

public void sort(int[] a) 
{
     for(int i = 0; i < n; i++) {
          int k = 0;
          for(int j = 1; j < n - i; j++) {
               if(a[j] < a[k]) k = j;
          }
          arrange(a, k);
     }
}

Hi. One possible algo..
Let the array size be n.
start = 0, end = n-1.
The first find smallest no. in [start, end]
give its position to Arrange.
start = 0, end = n-2.
Next find the smallest no. in [start, end] and give its position to Arrange.
Continue till end >= start.
No. of calls to Arrange is n.

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,i,position,temp;
    printf("\nhow many Elements you want ??");
    scanf("%d",&n);
    int *a=(int *)malloc(n*sizeof(int));
    printf("\n");
    printf("\nEnter:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++)
    {
        printf("\n%d",a[i]);
        printf("\n");
    }
    printf("\nEnter the position you want to operate on :");
    scanf("%d",&position);
    a[n]=a[position-1];
    for(i=position-1;i<n+1;i++)
        a[i]=a[i+1];
    printf("\new array :");
     for(i=0;i<n;i++)
    {
        printf("\n%d",a[i]);
        printf("\n");
    }
    return 0;
}

i dint use the arrange thing....anyway now whoever wants can see what i did....;) best of luck guys....

// sample.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include<iostream.h>

class Sort
{
private:
int *arr;
int n;

Sort()
{
arr = NULL;
n=0;
}

public:
Sort(int in_n)
{
arr = new int[in_n];
n = in_n;
}

void Arrange(int pos)
{
cout << " Big Position : "<< pos << endl;

int temp=arr[pos];

for(int i=pos; i<n-1; i++)
{
arr[i] = arr[i+1];
}

arr[n-1] = temp;
}

void sort()
{
int bigpos;
for(int i=n; i>0; i--)
{
bigpos = 0;
for(int j=1; j<i; j++)
{
if(arr[j] < arr[bigpos])
bigpos = j;
}

Arrange(bigpos);
}
}

void getData()
{
cout<<"Enter elements one by one:"<<endl;
for(int i=0; i<n; i++)
cin>>arr[i];
}

void putData()
{
cout << "Elements are : ";
for(int i=0; i<n; i++)
cout<<arr[i]<<",";
cout<<"\b."<<endl;
}

~Sort()
{
if(arr != NULL)
delete arr;
}
};


int main(int argc, char* argv[])
{
int n;

printf("\nhow many Elements you want ??");
cin >> n;

Sort s(n);
s.getData();
cout<<"Before Sorting an Array"<<endl;
s.putData();

s.sort();
cout<<"After Sorting an Array"<<endl;
s.putData();

return 0;
}

Problem is description of selection sort

just like quicksort.

1. find the pivot, n/2, and call Arrange(n/2).
2. scan the array, if the ith value is greater than the pivot value call Arrange(i)
also keep track of the position of pivot, each time we call Arrange(i)
3. now, values greater than pivot is in the right side of the pivot, and smaller or equal values are in the left.
4. recursively run the two sub-problems.

since quicksort has O(nlogn) average case complexity, number of Arrange() call will be nlogn on average.