Unordered & Ordered Array Programs

in #algorithms8 years ago (edited)

Complexities of Array Operations.
Linear Search - O(N)
Binary Search - O(logn)
Insertion on Unordered Array - O(1)
Insertion on Ordered Array - O(N)
Deletion on Unordered Array - O(N)
Deletion on Ordered Array - O(N)

Unordered Array Program:

package com.algorithm.arrays;

class UnOrderedArray {

private long[] a;
private int numberOfElements;

public UnOrderedArray(int maxSize) {
this.a = new long[maxSize];
}

public boolean find(long searchKey){
for(int ele=0;ele<numberOfElements;ele++){
if(a[ele]==searchKey)
return true;
}
return false;
}

public void insert(long value){
a[numberOfElements++] = value;
}

public boolean delete(long value){
int ele=0;
for(ele=0;ele<numberOfElements;ele++){
if(a[ele]==value)
break;
}

if(ele!=numberOfElements){
for(int k=ele;k<numberOfElements;k++){
if(k<numberOfElements-1)
a[k] = a[k+1];
else
a[k]=0;
}
numberOfElements--;
return true;
}
else{
return false;
}

}

public void display(){
for(int i=0;i<numberOfElements;i++){
System.out.println(a[i]);
}
}
}

public class UnOrderedArrayMain {
public static void main(String[] args){
UnOrderedArray arr = new UnOrderedArray(5);
arr.insert(1);arr.insert(2);arr.insert(3);arr.insert(4);arr.insert(5);

arr.display();

if(arr.find(3)){
System.out.println("Search value found");
}
else{
System.out.println("search value does not found");
}

arr.delete(3);

arr.display();
}
}

Ordered Array Program:
package com.algorithm.arrays;

class OrderedArray {

private long[] a;
private int numberOfElements;

public OrderedArray(int maxSize) {
this.a = new long[maxSize];
}

public int size(){
return numberOfElements;
}
public int find(long searchKey){
int lowerBound = 0;
int upperBound = numberOfElements-1;
while(true){
int currentIndex = (lowerBound + upperBound)/2;
if(a[currentIndex] == searchKey){
return currentIndex;
}
else if(lowerBound > upperBound)
return numberOfElements;
else if(a[currentIndex] > searchKey){
upperBound = currentIndex-1;
}
else
lowerBound = currentIndex+1;
}
}

public void insert(long value){

int i;
for(i=0;i<numberOfElements;i++){
//Linear Search Find Where new element fits
if(a[i]>value){
break;
}
}
for(int j=numberOfElements;j>i;j--){
a[j] = a[j-1];
}
a[i] = value;
numberOfElements++;
}

public boolean delete(long value){
int index = find(value);
if(index == numberOfElements){
return false;
}
else{
for(int k=index;k<numberOfElements;k++){
if(k<numberOfElements-1)
a[k] = a[k+1];
else
a[k]=0;
}
numberOfElements--;
return true;
}
}

public void display(){
for(int i=0;i<numberOfElements;i++){
System.out.println(a[i]);
}
}
}

public class OrderedArrayMain {
public static void main(String[] args){
OrderedArray arr = new OrderedArray(5);
arr.insert(100);arr.insert(26);arr.insert(3);arr.insert(1);arr.insert(5);

arr.display();

if(arr.find(100)!=arr.size()){
System.out.println("Search value found");
}
else{
System.out.println("search value does not found");
}

arr.delete(3);

arr.display();
}
}

Coin Marketplace

STEEM 0.24
TRX 0.25
JST 0.039
BTC 96247.25
ETH 3349.36
USDT 1.00
SBD 3.28