QUICK SORT

Quick sort is divide and conquer algorithm .Its one of the most influential algorithm of 20th century.

Its a top down approach every time a element  is taken and is fixed to some position and then from that fixed place array is portioned in two sub arrays(fixing the position of the pivot is termed as portioning the data) which a recursively portioned further.
It is in place sorting algorithm or in situ

Generally we make first element as the pivot in an array but this in all ready  sorted array does n^2 number of steps thus we prefer to do random shuffling to an array before passing it to quick sort function

Explanation-Here we have taken first element of  the array as the pivot we can take any element as the pivot or median for the best performance.If an array was sorted then we would have taken first element as pivot it would have resulted in worst performance.Thus while doing qsort we must put the given array to a shuffling function

Here split function helps in implementing the divide and conquer stuff by dividing the array into sub-arrays and qsort fixes the position of pivot

Time complexity

Best Case  nlogn (in best case number of compares are 1.39nlog(n))

Average Case   nlogn  (Depth of recursion is logarthmic)  

Worst Case n^2

Space Complexity O(n)

Stability* -In normal and efficient implementation of Quick sorting it is not  stable

Shuffling is needed for performance grantee

Optimizing  quick sort

• Use of extra array may help in partitioning but its not worth using it because it takes extra memory(and becomes same as merge sorting)
• it can be improved by using cut off ie after dividing array into small sub arrays and applying insertion sort, insertion sort handles the nearly sorted array efficiently and moreover it can sort the numbers during runtime
•  we can make pivot=median of the data and for large data we can get the median by taking sample the data

Comparison

In average case merge sorting do 39% more compares than quick sorting but quick sorting is faster than merge sorting because it has less data movement

Insertion and merge sort are stable while bubble selection and quick(in an efficient implimentation) are not stable

Insertion and merge sort are stable because in their algorithm we never make equal item pass or swap

What are stable sorting algorithms-:

In a stable sorting algorithms  relative order of the equal elements are maintained because we never swap the elements having the equal values(use full when we have lot many fields and need to arrange the data according to any field as required)

power of 2 in constant time

Checking if number can be presented in power of 2 in constant time:

Algorithm

Number which can be represented in power of 2 its binary form will have 1 only at msb while
number one less than it will have 0 at msb while all other will have 1.
For examble
64=1000000
63=0111111
Now if we multiply each bit of 64 with corresponding bit of 63 we will get 0

SOURCECODE
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int m=64;
int n=63;
if((m&n)==0)//bitwise operator
cout<<"yes number can be represented in power of two";
else
cout<<"cannot be represented in power of two";
getch();
}

Memory Layout in C

Types of memory

Memory layout in C

Whenever program is compiled five types of memories are given to the program to carry out its function

·         Text Segment

·         Initialized data segment

·         Uninitialized data segment

·         Stack

·         Heap

Text Segment-

Also known as the code segment

Contains executable instructions

Text segment is placed below stack and heap to prevent overflow

It is a read only memory so that it cannot be changed by accident

Initialize Data Segment-

Usually called Data Segment

It contains a static variables and global variables that are initialized by the program

It is a not a read only memory since it can be changed

Uninitialized Data segment-

Also known an bss segment (blog started by symbol)

It contains static and global variables which are initialized to zero or which are not explicitly initialized

Stack-

It contains the local or automatic variables

Even every memory required by the recursive functions also some from the stack memory.

Heap-

Heap memory is the segment where Dynamic memory allocation takes place

Heap area is shared by all the libraires and dynamically loaded modules in the process.

It has a disadvantage that it need to be manually freed thus leads to memory leaks or fault segment

Moreover variables allocated in stack memory are much faster to access than heap memory

MEMORY VIOLATIONS

MEMORY VIOLATIONS

Dangling Pointers and wild pointers are among  the few causes of memory safety violations.C and C++ provides with one of the most powerful tool programming world ever came with and this was Pointers but this gave programmer immense control over memory addresses and sometimes we try to acces memory which we are not suppose to access and this is called FAULT SEGMENT

Above we mentioned two types of memory violations-Dangling and Wild.
Dangling Pointers arises when some object is deleted or relocated or when some memory is made free without making pointer variable null. This happens  because even after deletion pointer points to the same location in memory even though the reference has been deleted or may be getting used for some other purposes

For example
void func()
{
    char *dp=malloc(1000)
free(dp); //here dp becomes dangling pointer
dp=NULL// now pd is null pointer and no longer a dangling pointer
}

Interesting thing about dangling pointers
char ch='a';
char *c=NULL;
c=&ch;
free(c);
printf("%c",*c);
It will still print the a because it still pointing to same memory location


Wild pointers-:
Main cause of it is not initializing the pointer variable to null when it is initially declared thus every pointer which has not been explicitly initializes is considered as a Wild pointers
For example

int f(int i)
{
char *dp//wild pointers
static char *scp//not a wild pointer because static initializes it to 0
}


SMART POINTERS
its a type of abstract data type and provides the additional features to the pointers such as automatic garbage collection and bound checking and is very useful in removing Dangling pointers.They set the pointers automatically to null when ther object is deleted. Java and C# dosent requires any smart pointers because they have there own garbage collection techniques
LISP was the first language having garbage collection