Meeting Point
All topics
Sorting
Sorting is a technique to re-order the data in increasing or decreasing order.
Data need not be integers; it can be strings, lists or anything which can have comparable objects.
Each programming language comes with an in-built Sort function.
In C, you can use quick sort as follows
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
here
- *base is pointer to the first element.
- nitems is the number of items to sort.
- size is the size of each element.
- compar is a compare function which can return -1 for less, 0 for equal and +1 for greater.
Sample Code in C
#include <stdio.h>
#include <stdlib.h>
int values[] = { 88, 56, 100, 2, 25 };
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main()
{
int n;
printf("Before sorting the list is: \n");
for( n = 0 ; n < 5; n++ )
{
printf("%d ", values[n]);
}
qsort(values, 5, sizeof(int), cmpfunc);
printf("\nAfter sorting the list is: \n");
for( n = 0 ; n < 5; n++ )
{
printf("%d ", values[n]);
}
return(0);
}
In C++ algorithm library comes with built in sort function.
example using array and a vector
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[] = {5,4,3,2,1};
vector <int> b(a,a+5); //initialised b using elements of a.
sort(a,a+5);
sort(b.begin(),b.end());
for (auto i :a) {
cout<<i<<" ";
}
cout<<endl;
for (auto i:b) {
cout<<i<<" ";
}
cout<<endl;
}
Note that you can also give your custom compare function in the third argument.
In order to reverse sort you can do
sort(b.rbegin(),b.rend());
In Python you can sort using
a.sort()
sometimes you can even define key which is like compare function.
arr = [[3, 4, 2, 1], [2, 1, 3, 4]]
arr.sort(key = lambda x : x[1]) #key should be a callable function
#here lambda is a returns the 1st element inside the list.
#arr is now [[2, 1, 3, 4], [3, 4, 2, 1]], sorted on 1st index.
Sample Code in Java :
import java.util.* ;
public class sorting{
public static void main(String []args){
Scanner sc = new Scanner(System.in) ;
int n ;
n = sc.nextInt() ;
int A[] = new int[n] ;
for(int i=0;i<n;i++)
A[i] = sc.nextInt() ;
Arrays.sort(A) ;
for(int i=0;i<n;i++)
System.out.print(A[i] + " ") ;
System.out.print("\n") ;
}
}
Manhattan Distance
Manhattan distance between two points is the sum of the absolute differences of their Cartesian coordinates.
For a space. Distance between and is given by :